Level 3. 전염병

문제설명

m x n 크기인 사무실이 있습니다. 사무실에는 전염병에 걸린 직원이 있는데, 이 직원은 매일 상하좌우로 병을 퍼트려 다른 직원을 감염시킵니다. 단, 백신을 접종한 직원은 면역력이 있어 감염되지 않습니다.

예를 들어 2x4 크기 사무실에서, 병에 걸린 직원의 위치가 (1,4), (2,2)이고 백신을 맞은 직원의 위치가 (1,2)입니다. 이때 백신을 맞은 직원을 제외한 모든 직원이 병에 감염되기 까지는 이틀이 소요됩니다.

사무실의 크기 m, n과 병에 걸린 직원의 위치 infests, 백신을 맞은 직원의 위치 vaccinateds가 매개변수로 주어집니다. 이때 백신을 맞은 직원을 제외한 모든 직원이 병에 감염되기까지 며칠이 걸리는지 return 하는 solution 함수를 완성해주세요.

 

입출력 예

m	n	infests	vaccinateds	result
2	4	[[1,4],[2,2]]	[[1,2]]	2
2	3	[[2,2]]	[[1,2],[2,1],[2,3]]	-1
2	2	[[1, 1], [2, 2]]	[[1, 2], [2, 1]]	0

 

 

#코드

from collections import deque
 
def solution(m, n, infests, vaccinateds):
    answer = 0
    day = m * n
    # m행 n열 크기의 배열을 만들고 기본값으로 False를 셋팅해준다.
    arr = [[False] * (n) for _ in range(m)]
 
    # 백신 접종자를 표기해준다. -2
    for yPos, xPos in vaccinateds:
        arr[yPos - 1][xPos - 1] = -2 
        day -= 1
 
 
    # 상, 하, 좌, 우
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]     
    deq = deque()  
 
 
    for row, col in infests:        
        deq.append((row - 1, col - 1, 0)) 
        arr[row - 1][col - 1] = True
        day -= 1
 
    while day > 0 and deq:        
        pop_row, pop_col, pop_day = deq.popleft()        
 
        for i in range(4):
            ny = dy[i] + pop_row
            nx = dx[i] + pop_col
 
            if 0 <= ny < m and 0 <= nx < n:
                if arr[ny][nx] != -2 and not arr[ny][nx]: 
                    arr[ny][nx] = True    
                    day -= 1
                    deq.append((ny, nx, pop_day + 1))
                    answer = pop_day + 1         
 
 
    return answer if day <= 0 else -1