[코딩테스트] 🦠 연구소3 - 백준 17142 | 삼성 SW 역량

백준 문제 링크

문제 유형

• 구현 문제
• 백트래킹
• BFS
• 조합

소요 시간

1시간 이상 못 품

회고

조합과 BFS까지는 할만 했으나, 백트래킹하는 법은 아직 모르겠다. BFS도 복습이 필요하다.

코드

func solution() {
    struct Point { let r: Int; let c: Int }

    let nm = readLine()!.split(separator: " ").map { Int($0)! }
    let N = nm[0], M = nm[1]

    var board = Array(repeating: Array(repeating: 0, count: N), count: N)
    var virusCandidates: [Point] = []
    var emptyCount = 0

    for i in 0..<N {
        let row = readLine()!.split(separator: " ").map { Int($0)! }
        for j in 0..<N {
            board[i][j] = row[j]
            if board[i][j] == 2 {
                virusCandidates.append(Point(r: i, c: j))
            } else if board[i][j] == 0 {
                emptyCount += 1
            }
        }
    }

    // 빈 칸이 애초에 없다면 0초
    if emptyCount == 0 {
        print(0)
        exit(0)
    }

    let dr = [-1, 1, 0, 0]
    let dc = [0, 0, -1, 1]

    let V = virusCandidates.count
    var comb = [Int]()  // 바이러스 후보의 인덱스 M개를 담음
    var answer = Int.max

    func bfs() {
        var dist = Array(repeating: Array(repeating: -1, count: N), count: N)
        var qR = [Int](), qC = [Int]() // 간단한 2배열 큐 (성능 좋음)
        var head = 0

        // 다중 시작점 세팅
        for idx in comb {
            let p = virusCandidates[idx]
            dist[p.r][p.c] = 0
            qR.append(p.r); qC.append(p.c)
        }

        var remainEmpty = emptyCount
        var maxTime = 0

        while head < qR.count {
            let r = qR[head], c = qC[head]; head += 1
            let curT = dist[r][c]

            // 가지치기: 이미 현재 최적 답보다 느리면 진행 의미 적음
            if answer != Int.max && curT >= answer { continue }

            for k in 0..<4 {
                let nr = r + dr[k], nc = c + dc[k]
                if nr < 0 || nr >= N || nc < 0 || nc >= N { continue }
                if board[nr][nc] == 1 { continue } // 벽
                if dist[nr][nc] != -1 { continue } // 이미 방문

                dist[nr][nc] = curT + 1
                qR.append(nr); qC.append(nc)

                if board[nr][nc] == 0 {
                    // 빈 칸 감염
                    remainEmpty -= 1
                    maxTime = max(maxTime, dist[nr][nc])
                    if remainEmpty == 0 {
                        // 모든 빈 칸 감염 완료 → 조기 종료 가능
                        answer = min(answer, maxTime)
                        return
                    }
                }
                // board == 2(비활성 바이러스)는 통로만 역할, 시간 갱신X
            }
        }
        // BFS 종료 후 빈 칸 남으면 실패(갱신 없음)
    }

    func choose(_ start: Int, _ picked: Int) {
        if picked == M {
            bfs()
            return
        }
        if start == V { return }

        for i in start..<V {
            comb.append(i)
            choose(i + 1, picked + 1)
            comb.removeLast()
        }
    }

    choose(0, 0)

    print(answer == Int.max ? -1 : answer)
}