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

👩🏻‍💻문제설명

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

문제요약

NxN 크기의 시험관이 있다. 모든 바이러스는 1번부터 K번까지 중 하나다.
모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식한다.
단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 빈칸으로만 증식할 수 있다.

S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하시오.
단, S초 후 바이러스가 존재하지 않는다면, 0을 출력한다.

입력

첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000)

둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다. 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다.

또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)

출력

S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력한다. 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.

예제 입력 1
3 3
1 0 2
0 0 0
3 0 0
2 3 2

예제 출력 1
3

예제 입력 2
3 3
1 0 2
0 0 0
3 0 0
1 2 2

예제 출력 2
0

✍️Idea Sketch

알고리즘 : BFS

바이러스는 1초마다 상, 하, 좌, 우의 방향으로 한 단계씩 증식한다. 여기서 BFS 알고리즘 문제임을 알 수 있다.

시간복잡도

그래프 크기 O(NM)

2차원 맵에서 상하좌우 4방향으로 움직일 수 있을 때, BFS 탐색 방법을 사용할 경우 시간복잡도는 그래프 크기 O(NM)이다.

이 문제에서도 바이러스는 빈칸으로만 증식하기 때문에, 상하좌우 탐색을 끝낸 시험관은 다시 방문할 필요가 없다. 따라서 시간복잡도는 O(NM)이다.

✍️내 소스코드

• 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식하므로 heap을 사용하였다.
• 새롭게 바이러스가 증식한 시험관은 "1초가 지난 뒤에" 방문해야한다. 즉 탐색 중인 queue가 아니라 new queue에 정보를 저장해야 한다.
• 1초가 지나면 새롭게 바이러스가 증식한 시험관을 방문한다. 따라서 queue는 new queue가 되고, new queue는 빈 배열로 초기화한다.
• S초가 지난 뒤 최종 target 지점 바이러스를 출력한다.

  import sys
  from copy import deepcopy
  from heapq import heappop, heappush

  si = sys.stdin.readline
  n, k = map(int, si().split())
  graph = [list(map(int, si().split())) for _ in range(n)]
  s, tx, ty = map(int, si().split())

  q, nq = [], []

  for i in range(n):
      for j in range(n):
          if graph[i][j]:
              heappush(q, (graph[i][j], i, j))

  for _ in range(s):
      while q:
          v, x, y = heappop(q)

          # 빈 자리가 있는 경우 -> graph 및 new queue에 추가
          for dx, dy in (1, 0), (0, 1), (-1, 0), (0, -1):
              nx, ny = x + dx, y + dy

              if (0 <= nx < n) and (0 <= ny < n) and graph[nx][ny] == 0:
                  graph[nx][ny] = v
                  heappush(nq, (v, nx, ny))

      q = deepcopy(nq)
      nq = []

  print(graph[tx-1][ty-1])