[백준 17142] 연구소3

1. 문제

www.acmicpc.net/problem/17142

17142번: 연구소 3

2. 접근 방법

일단 바이러스가 퍼지는거는 BFS로 했따.

 

그리고 바이러스 중 M개만 활성상태로 변경하기 때문에 총 바이러스 중 M개를 조합으로 뽑아내야한다.

 

조합으로 뽑아낸 다음 해당 바이러스들이 활성화 되었을 때 바이러스가 모두 퍼질 때까지 걸리는 시간을 구해야한다.

 

시간 제한이 0.5초라 시간을 어떻게 줄이느냐가 관건이다.

 

가지치기의 경우 현재 time이 minAns보다 클 경우와 현재 바이러스가 퍼진 갯수를 확인해서 바이러스가 다 퍼졌다면 종료를 해줬다.

 

참고로 이 문제에서 핵심은 활성바이러스와 비활성 바이러스가 있는 거다

왜냐면 비활성 바이러스도 바이러스라 비활성 바이러스까지 바이러스가 퍼지지 않아도 얘는 이미 바이러스다.

 

그래서 바이러스가 다 퍼졌는지 안퍼졌는지 확인하는게 골치아팠는데

그냥 바이러스와 벽의 갯수를 확인해서 빈칸의 갯수를 세줘서 이거 총 합이 N*N이 될 때 == 바이러스가 다 퍼졌을 때 로 구했다.

정확히는 N*N에서 한개씩 빼줘서 virus_cnt_total이라는 변수가 0이 될 때 종료를 시켜줬다.

 

3. 코드

python

from collections import deque

def comb(start, cnt):
    global M, minAns, virus_temp
    if cnt == M:
        ans = bfs(virus_temp)
        if ans != -1:
            minAns = min(minAns, ans)

    else:
        for i in range(start, len(viruses)):
            virus_temp.append(viruses[i])
            comb(i+1, cnt+1)
            virus_temp.pop()

def bfs(lst):
    global visited, virus_cnt_total
    virus_cnt = virus_cnt_total
    if virus_cnt == 0:
        return 0
    dx, dy = (0, 1, 0, -1), (1, 0, -1, 0)
    temp_visited = [visited[i][:] for i in range(N)]
    q = deque()
    for i in range(len(lst)):
        _x, _y = lst[i]
        q.append((_x, _y, 1))
        # 처음 cnt 값은 1로 시작
        temp_visited[_y][_x] = 1
    while q:
        x, y, cnt = q.popleft()
        if cnt > minAns:
            return -1
        for i in range(4):
            tx = x + dx[i]
            ty = y + dy[i]
            if 0 <= tx < N and 0 <= ty < N:
                if temp_visited[ty][tx] == 0 or temp_visited[ty][tx] == -2:
                    if temp_visited[ty][tx] == 0:
                        virus_cnt -= 1
                        if virus_cnt == 0:
                            return cnt
                    q.append((tx, ty, cnt+1))
                    temp_visited[ty][tx] = cnt+1
    if virus_cnt == 0:
        return cnt-1
    else:
        return -1

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[0]*N for _ in range(N)]
viruses = []
virus_temp = []
minAns = 1e9
virus_cnt_total = N*N

for y in range(N):
    for x in range(N):
        if board[y][x] == 1:
            visited[y][x] = -1
            virus_cnt_total -= 1
        elif board[y][x] == 2:
            visited[y][x] = -2
            viruses.append((x, y))
            virus_cnt_total -= 1
if virus_cnt_total > 0:
    comb(0, 0)
    if minAns == 1e9:
        minAns = -1
    print(minAns)
else:
    print(0)

4. 마치며

.