[백준 python] 18405번 경쟁적 전염 - DFS/BFS

[백준 python] 18405번 경쟁적 전염 - DFS/BFS

레벨: 실버1

언어: python

---

문제풀러가기

📋풀이 코드

import sys
from collections import deque

input = sys.stdin.readline

n, k = map(int, input().split(' '))
graph = [list(map(int, input().split(' '))) for _ in range(n)]

t_s, t_x, t_y = map(int, input().split(' '))

virus = []
for i in range(n):
  for j in range(n):
    if graph[i][j] != 0:
      # 바이러스 번호, 시간, X 위치, Y 위치
      virus.append((graph[i][j],0,i,j))

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# 숫자가 낮은 바이러스 부터 실시
virus.sort()
q = deque(virus)

while q:
  v_num, s, x, y = q.popleft()
  if s == t_s:
    break

  for i in range(4):
    nx = x+dx[i]
    ny = y+dy[i]
    if 0<= nx < n and 0<= ny < n:
      if graph[nx][ny] ==0:
        graph[nx][ny] = v_num
        q.append((v_num,s+1,nx,ny))

print(graph[t_x-1][t_y-1])

📑풀이 과정

이 문제는 BFS로 풀 수 있다.

queue에 바이러스 번호, 시간, 위치를 넣어서 BFS 탐색을 하면 된다.

virus.append((graph[i][j],0,i,j))
virus라는 리스트에 바이러스의 번호, 시간, X위치, Y위치를 삽입한다.

그리고 번호가 작은 순서로 바이러스가 퍼지기에 정렬을 하여 queue에 삽입한다.

 

그 후 queue에서 popleft로 꺼내어 BFS 탐색을 하고 탐색을 할 때 시간을 +1 하여준다.
시간(s)가 t_s와 같으면 BFS 탐색을 멈추고 문제에서 요구한 위치의 바이러스를 출력한다.

---

DFS/BFS는 계속해서 풀어도 아직 감이 오지 않는다.
처음에는 for문을 s 시간 만큼 돌릴려고 했는데 잘 되지 않았다.

그 후 아무리해도 접근 법이 떠오르지 않아 고민 끝에 문제의 풀이를 보고 접근법을 확인한 후에서야 코드를 작성할 수 있었다.
아직까지 DFS/BFS는 연습이 많이 필요한 유형인것 같다.