[ BOJ ] DFS/BFS - 경쟁적 전염

문제링크

18405번: 경쟁적 전염

문제설명

N*N 크기의 시험관에 1~K번까지 K개의 바이러스가 각 칸에 위치해있다. 1초마다 상하좌우로 증식하고, 이미 바이러스가 있는 칸에는 증식할 수 없고, 번호가 낮은 바이러스가 먼저 증식한다.

S초뒤 좌표 (x,y)에 위치한 바이러스의 번호는?

IN

• 시험관 크기 바이러스개수
• 시험관속 바이러스 배치
• S X Y

OUT
S초뒤 좌표 x,y에 위치한 바이러스 번호

문제풀이

시도 1

import sys
input = sys.stdin.readline

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

n, k = map(int, input().split())
path = []
virus = [[] for _ in range((k+1))]

for i in range(n):
    tmp = list(map(int, input().split()))
    for j in range(n):
        if tmp[j] != 0:
            virus[tmp[j]].append((i,j))
    path.append(tmp)

S, X, Y = map(int, input().split())
time = 0
while time < S:
    for i in range(1, k+1):
        for j in range(len(virus[i])):
            #i번부터 k번까지의 바이러스에 대해서
            x,y = virus[i][j]

            #상하좌우 증식
            for k in range(4):
                if 0<=x+dx[k]<n and 0<=y+dy[k]<n:
                    if path[x+dx[k]][y+dy[k]] == 0:
                        path[x+dx[k]][y+dy[k]] = i
                        virus[i].append((x+dx[k], y+dy[k]))
            
    time += 1
    #print(path)
print(path[X-1][Y-1])

→ 시간초과가 났다. 이미 상하좌우를 검사한 칸에 대해서는 다시 검사할 필요가 없는데 검사했기때문

시도 2

import sys
import heapq
input = sys.stdin.readline

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

n, k = map(int, input().split())
path = []
virus = []
time = 0

for i in range(n):
    tmp = list(map(int, input().split()))
    for j in range(n):
        if tmp[j] != 0:
            heapq.heappush(virus, [0, tmp[j], i, j])
    path.append(tmp)

S, X, Y = map(int, input().split())
while virus:
    time, virusNum, x, y = heapq.heappop(virus)
    if time >= S:
        break
    #상하좌우 증식
    for k in range(4):
        if 0<=x+dx[k]<n and 0<=y+dy[k]<n:
            if path[x+dx[k]][y+dy[k]] == 0:
                path[x+dx[k]][y+dy[k]] = virusNum
                heapq.heappush(virus, [time+1, virusNum, x+dx[k], y+dy[k]])
    #print(virus)   
print(path[X-1][Y-1])

작은 바이러스부터 우선적으로 처리해야 하므로 heap을 이용해서 풀었다. 초를 어떻게 세면 좋을지 고민하다가, heap의 첫번째 원소로 시간을 넣어서 시간순으로 우선 정렬된 후 바이러스 번호로 정렬되도록 하였다.