[이것이 코딩 테스트다 with Python] Chapter 13. DFS/BFS - 경쟁적 전염

< 경쟁적 전염 >

 

💬 문제 설명

NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다. 시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.

....

 

입력	출력
3  3   1  0  2   0  0  0   3  0  0   2  3  2	3
3  3   1  0  2   0  0  0   3  0  0   1  2  2	0

💬 입력 조건

• 첫째 줄에 N 지도의 크기, K 바이러스 번호 ( 1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000 )
  
• 둘째 줄부터 N개의 줄에 시험관 정보
• N + 2 번째 줄 S 초,  X  Y 좌표 (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)

💬 출력 조건

• 첫S초 뒤에 ( X, Y )에 존재하는 바이러스의 종류를 출력

---

✍ 문제요약

N X N 크기의 시험관이 주어진다. 특정한 위치에 1번부터 K번 까지의 바이러스가 존재한다. 바이러스는 1초마다 상하좌우로 퍼져나가고, 이 때 번호가 작은 것이 먼저 퍼져간다. S초 후에 ( X, Y ) 좌표에 있는 바이러스의 종류를 출력하여라.

💯 문제링크

백준18405 문제와 동일하다.

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

18405번: 경쟁적 전염

---

✅  문제 풀이

• 바이러스가 퍼져나가는 함수 BFS를 만들고, S초 반복 해주었다.
• 바이러스 종류와 좌표를 리스트에 담아, 바이러스 번호가 낮은 순으로 오름차순 정렬한다.
• 번호 순으로 바이러스를 상하좌우로 이동 시키며 이동한 좌표를 새로운 리스트에 담아 반환한다.
• 이를 S초 동안 반복하여, 원하는 좌표의 값이 들어오면 정지한다.

import sys ; sys.stdin = open("input.txt")
from collections import deque
input = sys.stdin.readline

def BFS():
    Q_tmp = []
    while Q:
        virus, r, c = Q.popleft()
        for dr, dc in ((-1,0),(0,1),(1,0),(0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < N and 0 <= nc < N and not G[nr][nc]:
                G[nr][nc] = virus            # 그래프에 바이러스 번호 표시
                Q_tmp.append((virus,nr,nc))  # 이동한 위치와 바이러스를 다른 리스트에 저장
    return Q_tmp                             # 그 리스트를 반환

N, K = map(int,input().split())              # N : 그래프 크기 NxN, K : 바이러스 번호
G, Q = [], []

for r in range(N):
    tmp = list(map(int,input().split()))
    G.append(tmp)
    for c in range(N):
        if tmp[c] : Q.append((tmp[c], r, c))  # (바이러스 번호, 좌표x, 좌표y)

Q = deque(sorted(Q,key = lambda x:x[0]))      # 바이러스 번호 순 오름차순
S, X, Y = map(int,input().split())

for _ in range(S):                   # S초 만큼 BFS 실행
    Q = deque(BFS())                 # 반환받은 리스트를 Q에 저장하고 다시 BFS
    if G[X - 1][Y - 1]: break        # 원하는 좌표에 바이러스 퍼지면 종료
print(G[X-1][Y-1])