백준 17142 연구소 3

출처: www.acmicpc.net/problem/17142

분류: 완전탐색, BFS, DFS

---

접근방식

조합과 BFS를 사용해 해결할 수는 문제였습니다.

바이러스가 활성화될 수 있는 지역과 최대 활성화시킬 수 있는 바이러스의 수가 주어졌을 때,
활성화 바이러스의 조합을 뽑아 BFS를 돌려 최단 거리를 계산합니다.

활성화 바이러스의 조합은 순서 상관없이 뽑는 경우의 수이기 때문에 순열이 아닌 조합으로 처리해줘야 합니다!

var selected = [Point]()
func selectVirus(curr: Int) {
    if selected.count == nm[1] {
        let time = infectTime(selected)
        if time != -1 {
            if minimumTime == -1 {
                minimumTime = time
            } else if minimumTime > time {
                minimumTime = time
            }
        }
        return
    }
    
    guard curr < virusArea.count else { return }
    selected.append(virusArea[curr])
    selectVirus(curr: curr+1)
    selected.removeLast()
    selectVirus(curr: curr+1)
}

조합에 대한 자세한 설명이 궁금하시면 여기를 참고해주세요 :)

주의할 점은 활성화되지 않은 바이러스 지역은 시간계산에 포함시키면 안 된다는 것입니다.

2 2
2 2 

와 같이 모두 바이러스 지역일 경우에 하나만 활성화 시켜서

2 *
* *

를 생각해야 할 때 걸리는 시간은 0입니다.

저는 바이러스 지역이어도 똑같이 큐에 담아 BFS 계산을 해주고 마지막에 최대 시간을 계산해줄 때만 바이러스 가능 지역은 포함하지 않는 방식으로 구현해줬습니다.

// map에서 1로 벽일 경우만 무시해주고 나머지는 똑같이 큐에 담으면서 거리를 계산함
for next in nexts(curr) where isInRange(next) && map[next.r][next.c] != 1 {
  guard dist[next.r][next.c] < 0 else { continue }
  queue.append(next)
  dist[next.r][next.c] = dist[curr.r][curr.c] + 1
}

// 거리를 계산할 때는 map이 0인 지역만 가지고 처리
var maxTime = 0
for r in 0..<nm[0] {
    for c in 0..<nm[0] {
        guard map[r][c] == 0 else { continue }
        if dist[r][c] == -1 {
            return -1
        } else if maxTime < dist[r][c] {
            maxTime = dist[r][c]
        }
    }
}

 

 

 

배운점

처음에 생각없이 조합이 아니라 순열을 계산해버려서 어마어마한 시간초과를 겪었다. 

그리고 조합에서도 가드처리를 앞에서부터 막아버려서 마지막 수를 처리해주지 못해 틀렸었다. 주의하자!!

아직도 조합 + bfs, dfs + bfs 등등 bfs를 자연스럽게 섞어서 해결해야 하는 문제들에 덜 익숙한 것 같다.