알고리즘_코딩테스트/이것이 코딩테스트다
[DFS/BFS] 경쟁적 전염
논곰
2021. 12. 16. 00:36
"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.
소요시간: 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. 코멘트
- 코딩 테스트는 '결국에 하나도 손을 못 대겠다'는 없는 것 같고, 키 아이디어를 어떻게 생각하고 구현할 것인지에 관한 싸움인 거 같다.