백준 알고리즘 18405: 경쟁적 전염(Python)

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

18405번: 경쟁적 전염

문제 해결을 위한 과정

이 문제의 경우 BFS만 알고 있다면 쉽게 해결할 수 있는 문제입니다. 그래프를 입력을 받을 때 0이 아닌 즉 바이러스가 있는 부분들에 대한 좌표를 따로 virus라는 리스트를 만들어서 그 리스트에 있는 좌표값들에 대해서만 BFS를 수행하면 되는 것입니다. 이때 문제에서 알 수 있듯이 이미 바이러스가 퍼진 구역에는 어떠한 바이러스도 퍼질 수 없으므로 그래프에서 해당 좌표의 지역이 0 인 경우 즉 비어있는 경우만 탐색을 할 수 있습니다. 또한 문제에서 숫자가 낮은 바이러스가 우선적으로 퍼지는 조건이 있습니다. 이 경우는 문제 해결을 위한 팁에서 알아보겠습니다.

---

문제 해결을 위한 팁

저의 경우는 바이러스가 있는 곳을 리스트에 넣을때 해당 좌표에 있는 바이러스에 값과 좌표를 리스트에 저장했습니다. 만약 입력 예시 1의 경우 0 행 0열에 있는 바이러스가 1 이기 때문에 virus.append((graph[i][j], i, j)) 이렇게 저장했습니다. 이 형태로 저장을 하게 되면 입력을 다 한 후 virus.sort()를 하게 되면 맨 앞 원소를 기준으로 오름차순으로 정렬을 하기 때문에 별도의 처리 없이 오름차순 된 virus 리스트 그대로 BFS를 수행하면 숫자가 낮은 바이러스부터 우선적으로 탐색을 할 수 있습니다.

---

소스코드

 

from collections import deque
 
N, K = map(int, input().split())
graph = []
virus = []
for i in range(N):
  graph.append(list(map(int, input().split())))
  for j in range(N):
    if graph[i][j] != 0:
      virus.append(((graph[i][j], i, j)))
S, X, Y = map(int, input().split())
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
def bfs(s, X, Y):
  q = deque(virus)
  count = 0
  while q:
    if count == s:
      break
    for _ in range(len(q)):
      prev, x, y = q.popleft()
      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] = graph[x][y]
            q.append((graph[nx][ny], nx, ny))
    count += 1
  return graph[X-1][Y-1]
 
virus.sort()
print(bfs(S, X, Y))