[파이썬/python] 백준 - 18405 경쟁적 전염

문제

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

---

문제 설명

1.   N*N 크기의 시험관이 입력으로 들어온다.
2. 시험관 배열에는 종류가 다른 바이러스들이 존재한다.
   1. 바이러스의 종류는 1~K번 중 하나에 속한다.
3.   하루가 지날 때 마다 바이러스가 상,하,좌,우로 증식된다.
   1. 이 때 바이러스의 번호가 낮은 것 부터 증식한다.
   2. 다른 바이러스가 존재한다면, 그 위치로는 증식하지 않는다.
4. S초가 지났을 때, Y,X 위치에 존재하는 바이러스를 출력한다.

 

---

풀이

너비 우선 탐색(BFS)는 먼저 방문한 위치들을 먼저 탐색한다. 즉 시작할 때 시험관에 존재하는 바이러스들을 오름차순으로 정렬시킨 후 큐에 입력한다면, 무조건 바이러스들은 낮은 번호부터 증식하게 될 것이다.

이러한 상황에서 입력으로 받은 S초까지 BFS를 진행하도록 구현했다.  

1. 시험관 배열을 완전 탐색하여 바이러스들의 위치와 초기 시간을 queue 배열에 입력한다.
2. queue 배열을 바이러스 종류 오름차순으로 정렬한 후, deque 구조로 변경한다.
3. BFS 탐색을 통해 queue에서 꺼낸 데이터가 S초일 때 까지 탐색을 진행한다.
4. y,x 위치의 바이러스 번호를 출력한다. 

---

코드

import sys
from collections import deque
input = sys.stdin.readline

n,k = map(int,input().split())

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

s,y,x = map(int,input().split())
y,x = y-1,x-1

queue = []
for i in range(n):
    for j in range(n):
        if board[i][j] != 0:
            queue.append((i,j,board[i][j],0))
        board[i][j] = [board[i][j],0]



queue = deque(sorted(queue, key = lambda x: x[2]))

dy = [0,1,0,-1]
dx = [1,0,-1,0]
def bfs():

    while queue:
        y,x,v,t = queue.popleft()
        if t > s-1:
            return
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if ny < 0 or ny > n-1 or nx < 0 or nx > n-1 or board[ny][nx][0]:
                continue
            board[ny][nx] = [v,t+1]
            queue.append((ny,nx,v,t+1))

bfs()
print(board[y][x][0])

 

---

시간복잡도

• 초기 바이러스를 찾기 위해 완전 탐색을 진행한다. 따라서 $N^2$의 시간이 소요된다.
• BFS를 진행할 때 최악의 경우 모든 위치를 탐색하는 경우이기 때문에 $N^2$의 시간이 소요된다.
• 따라서 총$ 2*N^2$이지만 상수를 제외하고  $O(N^2),$ 최악의 경우 $N = 200$이므로 약 $O(10^4)$의 시간복잡도를 가진다.