[백준] #18405 경쟁적 전염 (Python)

1. 문제 설명

문제 링크

• 입력
  • 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어짐
  • 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어짐 : 존재하는 바이러스의 번호가 공백을 기준으로 주어짐, 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어짐 ( 모든 바이러스의 번호는 K이하의 자연수)
  • N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어짐
• 출력 : S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력, 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력

2. 코드

solution1.py

from collections import deque
import sys
input = sys.stdin.readline

N,K = map(int, input().split())
graph = []
data = [] # 바이러스종류 저장
for i in range(N):
    graph.append(list(map(int, input().split())))
    for j in range(N):
        #해당 위치에 바이러스가 존재하는 경우
        if graph[i][j] !=0:
            #바이러스종류, 초, 위치 x, 위치 y
            data.append((graph[i][j],0,i,j))

data.sort()

#ex1 : deque([(1, 0, 0, 0), (2, 0, 0, 2), (3, 0, 2, 0)])
q = deque(data)

target_s, target_x, target_y = map(int, input().split()) #초, 위치 x, 위치 y

#상하좌우
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

while q:
    virus, s, x, y = q.popleft()
    #s초가 지나거나, 큐가 빌때까지 반복
    if s == target_s:
        break
    #현재 노드에서 4가지 위치를 각각 확인
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        #해당 위치로 이동할 수 있는 경우
        if 0 <= nx and nx < N and 0 <=ny  and ny < N:
            #아직 방문하지 않은 위치라면, 그 위치에 바이러스 넣기
            if graph[nx][ny] == 0:
                graph[nx][ny] = virus
                q.append((virus, s+1, nx,ny))

print(graph[target_x -1][target_y -1])

3. 회고

Q. 문제를 보고 든 생각

• 제공된 시험관 정보를 bfs를 적용하려면 어떤 방식으로 저장해야하지? 인접리스트 형태로 저장하기엔 어려운 것 같은데...
  • 2차원 리스트에 그냥 담으면 됨!
• 모든 간선의 비용이 1이기 때문에 BFS를 통한 최단거리 계산이 가능
  • BFS로 풀기로 결정

Q. 코드를 참고하면서 들었던 의문점들

1. 어떻게 작은 바이러스가 위치를 선점을 했는지?

• 바이러스가 낮은 번호부터 증식하기 때문에 큐에 낮은 번호의 바이러스부터 넣어주기만 하면 자동으로 BFS를 수행 시에 낮은 번호부터 증식하는 방식이 적용가능하다.

2. 큐에서 꺼낼때 순서는?

• 처음엔 바이러스가 있는 곳 위치를 순서대로 꺼냄
• 그 후에는 새롭게 업데이트 된 곳에서의 (바이러스, 초,x,y)를 큐에 넣고, 존재하던 바이러스를 기준으로 상하좌우를 다 탐색한 후에는 새롭게 넣은 (바이러스, 초,x,y)를 꺼냄

3. 그렇다면 왜 이미 존재하는 곳(0이 아닌 곳)은 큐에 넣어주지 않았는가?

• ??? (미해결)

4. 시간은 어떻게 count?

• 큐에 시간정보를 저장해두고, 저장해둔 각 바이러스는 초기시간이 0, 새롭게 업데이트하는 노드가 발생하면 +1해서 시간 업데이트 후, 큐에 넣어준다.
• 이렇게 하면 큐에서 꺼냈을 때, 해당 노드는 시간이 증가한 상태, 종류조건을 확인하는데 도움

5. 종료조건?

• 큐에서 새로운 노드를 꺼냈는데, 그게 만약 S초라면 거기까지만 진행하고 그 이후 진행은 막아야하므로, break
• 만약 주어진 S초 전에 큐 안에 값이 더이상 존재하지 않아도 break, 원하는 시간 이전에 이미 모든 시험관에 바이러스가 전염되었기 때문에, 그 상태에서 결과를 탐색

4. 참고

https://www.youtube.com/watch?v=PqzyFDUnbrY