[17번] 경쟁적 전염

https://www.acmicpc.net/problem/18405

18405번: 경쟁적 전염

경쟁적 전염: K초 후 바이러스 전파결과 확인

 

• 탐색방향: 상하좌우
• 탐색조건: MAP == 0
• 탐색결과: MAP = 1, 2, 3, ... (바이러스 영역으로 변경)
• 출발점: 바이러스 위치들
• 알고리즘 선택: S초까지 탐색 => BFS

 

import collections

N, K = map(int, input().split())
MAP = []
viruses = []
for r in range(N):
    MAP.append(list(map(int, input().split())))
    for c in range(N):
        if MAP[r][c] != 0:
            viruses.append((MAP[r][c], 0, r, c))
viruses.sort()  # 낮은 바이러스 순서로 전파

S, X, Y = map(int, input().split())

# 바이러스 전파 (BFS)
qu = collections.deque(viruses)
while qu:
    vtype, second, x, y = qu.popleft()
    if second == S:  # S초까지 탐색
        break

    for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < N and 0 <= ny < N:
            if MAP[nx][ny] == 0:
                MAP[nx][ny] = vtype
                qu.append((vtype, second + 1, nx, ny))

print(MAP[X - 1][Y - 1])  # 3

3 3
1 0 2
0 0 0
3 0 0
2 3 2