[DFS/BFS] 경쟁적 전염

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간:  26분

1. 문제 설명

- 여러 바이러스가 존재하는데 바이러스는 인접한 위치로 전파가 된다. 특정 시간 초 이후에 좌표를 입력으로 줄 때, 해당 좌표의 값은 무엇인지 묻는 문제

2. 접근 방식

- BFS를 활용해서 문제를 풀면 되겠다고 생각을 했다.

- 초기에 그래프를 생성할 때 어떤 식으로 그래프를 생성하는 지에 대한 고민이 필요한 문제라고 생각을 했다. 

- 초기 데이터를 (바이러스 종류, 시간, x좌표, y좌표)를 튜플형태로 묶어서 리스트에 넣어주는 부분을 알고나니 수월하게 문제를 풀 수 있었다. 

3. 코드

from collections import deque
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:
            data.append((graph[i][j], 0, i, j)) #  바이러스의 종류, 시간, 위치 x y
            # 초기값 설정
data.sort() # 낮은 거 먼저 나와야 되니깐 
q = deque(data)

target_s, target_x, target_y = map(int, input().split())

dx = [-1, 0, 1, 0] # 북, 동, 남, 서
dy = [0, 1, 0, -1]

for s in range(target_s): # s초 동안 진행
    while q: 
        virus, time, i, j = q.popleft()
        # 네 방향을 확인해서 자기로 전염시킨다.
        if time != s: 
            break
        for idx in range(4):
            tmp_x = i+dx[idx]
            tmp_y = j+dy[idx]
            if tmp_x>=0 and tmp_x<n and tmp_y>=0 and tmp_y <n:
                if graph[tmp_x][tmp_y] == 0:
                    graph[tmp_x][tmp_y] = virus
                    q.append((virus, s+1, tmp_x, tmp_y))

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

4. 코멘트

- 코딩 테스트는 '결국에 하나도 손을 못 대겠다'는 없는 것 같고, 키 아이디어를 어떻게 생각하고 구현할 것인지에 관한 싸움인 거 같다.