[백준 17142][Python] 연구소 3

문제 바로가기

17142번: 연구소 3

 

Logic

1. 바이러스는 Virus 리스트에 담는다. 이 중 M개를 골라 조합을 만들고, activate_Virus에 담는다.

2. 바이러스가 아직 안 퍼진 곳(즉, Map에서 0인 부분)의 count를 세어서 virus_count에 저장한다.

3. 활성화 바이러스 조합 각각에 대하여 bfs(virus) 함수를 실행한다.

   3-1. 활성화 바이러스를 queue에 넣는다.

   3-2. 현재 queue에 들어있는 원소들에 대해서만 한다. -> level 을 계산해주기 위해서

   3-3. queue를 pop 하고, 이 원소에 대해 4방향으로 바이러스를 퍼뜨릴 수 있는 지 검사한다.

   ​ 그 자리가 빈 공간이라면, v_c의 개수를 하나 줄여준다. -> v_c가 퍼뜨려야할 바이러스의 개수이므로

   ​ 그 자리가 비활성화 바이러스라면, v_c 개수 줄이는 작업은 하면 안된다.

   ​ queue에 추가하고 visited를 True로 변경한다.

   if(isIn(ny, nx) and not(visited[ny][nx]) and Map[ny][nx] != 1): # map에 포함되고 들리지 않은 곳이고 벽이 아니면
       visited[ny][nx] = True
       if Map[ny][nx] == 0:
           v_c -= 1                    
       if v_c == 0:
           return level
       queue.append([ny, nx])

   3-4. v_c가 0이 되면 바이러스가 모든 공간으로 퍼졌다는 뜻이므로, 그 때의 level을 return 한다.

4. 최종적인 답을 구한다. 모든 경우에 -1이 아니라면, min값을 출력한다.

 

Review

흑흑 아무데서나 마음대로 deepcopy 쓰지 맙시다.......

시간 초과 난리 났었는데 이거 때문인 거 알고 너무 슬펐습니다....

 

Code

from itertools import combinations
from collections import deque

def isIn(y, x):
    if y >= 0 and x >= 0 and y < N and x < N:
        return True
    return False

def bfs(virus):
    global v_c
    visited = [[False]*N for _ in range(N)]
    pos = [[1,0],[-1,0],[0,1],[0,-1]]
    level = 0
    queue = deque(virus)

    while queue:
        level += 1
        for _ in range(len(queue)):
            curr = queue.popleft()
            for i in range(4):
                ny = curr[0] + pos[i][0]
                nx = curr[1] + pos[i][1]

                if(isIn(ny, nx) and not(visited[ny][nx]) and Map[ny][nx] != 1): # map에 포함되고 들리지 않은 곳이고 벽이 아니면
                    visited[ny][nx] = True
                    if Map[ny][nx] == 0:
                        v_c -= 1                    
                    if v_c == 0:
                        return level
                    queue.append([ny, nx])

    return -1


N, M = map(int, input().split())
Map = [[int(x) for x in input().split()]for y in range(N)]

Virus = []
activate_Virus = []

flag = 0
answer = 1000000
virus_cnt = 0
required_cnt = 0

for i in range(N):
    for j in range(N):
        if(Map[i][j] == 0):
            flag = 1
            virus_cnt += 1
        if(Map[i][j] == 2):
            Virus.append([i, j])

if flag == 0:
    print(0)

else:
    activate_Virus = list(combinations(Virus, M))
    # print(activate_Virus)

    for i in range(len(activate_Virus)):
        v_c = virus_cnt
        maxValue = bfs(activate_Virus[i])
        if maxValue != -1:
            answer = min(answer, maxValue)

    if(answer == 1000000):
        print(-1)
    else:
        print(answer)