Level 3. 전염병

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

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

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

제한사항

• m과 n은 1 이상 300 이하인 자연수입니다.
• infests의 길이는 1 이상 m * n 이하입니다.
  • infests의 원소는 [a, b] 형식이며, 1 ≤ a ≤ m, 1 ≤ b ≤ n입니다.
  • infests에는 같은 원소가 두 번 이상 들어있지 않습니다.
• vaccinateds는 길이가 1 이상 m * n 이하입니다.
  • vaccinateds의 원소는 [a, b] 형식이며, 1 ≤ a ≤ m, 1 ≤ b ≤ n입니다.
  • vaccinateds에는 같은 원소가 두 번 이상 들어있지 않습니다.
• 백신을 맞은 직원이 병에 걸린 경우는 주어지지 않습니다.
• 병을 아무리 퍼트려도 백신을 맞은 직원을 제외한 모든 직원이 병에 감염될 수 없다면 -1을 리턴합니다.

입출력 예

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

다른 사람의 풀이

• BFS 알고리즘을 사용해야 한다.

import queue

def valid(x, y, n, m):
    return 0 <= x < m and 0 <= y < n

def solution(m, n, infests, vaccinateds):
    answer = 0
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    
    q = queue.Queue()
    visited = [[False] * n for _ in range(m)]
    num_emp = m * n # 빈칸 수
    
    for vaccinated in vaccinateds:
        a, b = vaccinated
        visited[a - 1][b - 1] = True
        num_emp -= 1
    
    for infest in infests:
        a, b = infest
        visited[a - 1][b - 1] = True
        num_emp -= 1
        q.put([a - 1, b - 1, 0])
    
    while num_emp > 0 and q.qsize() > 0:
        cur_x, cur_y, cur_day = q.get()
        for d in range(4):
            next_x = cur_x + dx[d]
            next_y = cur_y + dy[d]
            if not valid(next_x, next_y, n, m) or visited[next_x][next_y]:
                continue
            visited[next_x][next_y] = True
            num_emp -= 1
            q.put([next_x, next_y, cur_day + 1])
            answer = cur_day + 1
            
    return answer if num_emp <= 0 else -1