[백준] 18405번: 경쟁적 전염 Python (DFS, BFS) | LIM

이 문제는 BFS를 이용하여 풀었다. 

생각보다 이 문제는 간단하게 풀 수 있었다. 

 

먼저, 바이러스가 존재하는 위치와 그 위치에 바이러스 값을 저장했다.

또한, 바이러스 숫자가 작을수록 우선수위를 갖기 때문에 바이러스 숫자가 작은 순서대로 sorting 해주었다.

 

popleft()를 통해 앞에 있는 것(바이러스 숫자가 작은것)부터 뽑아내며 상하좌우로 퍼지게 하였다. 

퍼지게 한 후 바이러스가 전염된 부분의 바이러스 값과 인덱스를 기존 virusIndex에다가 뒤로 저장하였다. 맨 처음에 순서대로 sorting 해주었기 때문에 추후에 저장되는 바이러스 값은 자동으로 정렬이 되어 있다.

 

기존에 있던 바이러스가 모두 popleft()를 통해 사라지고 그 바이러스를 통해 전염된 바이러스와 인덱스만 남게 되면 시간을 1초 더해준다. 

주어진 시간까지 반복하면서 중간에 만약 문제에서 주어진 위치에 바이러스가 퍼지게 되면 굳이 정해진 시간까지 진행할 필요가 없기 때문에 바로 return 해주었다. (문제에서 기존에 바이러스가 퍼진 곳은 다른 바이러스가 퍼질 수 없다고 명시되어 있다.)

from collections import deque
import sys

input = sys.stdin.readline
data = []
n,k = map(int,input().split())

for _ in range(n):
    data.append(list(map(int,input().split())))
s,x,y = map(int,input().split())

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

def getIndex(map):
    virusIndex = []
    for i in range(n):
        for j in range(n):
            if map[i][j] != 0:
                virusIndex.append([map[i][j],i,j])
    virusIndex.sort(key=lambda x: x[0])
    return virusIndex

def spreadVirus(data):
    virusIndex = deque(getIndex(data))
    time = 0
    while time < s:
        count_virus = len(virusIndex)
        pop_virus = 0
        while virusIndex:
            idx = virusIndex.popleft()
            pop_virus += 1
            for i in range(4):
                nx = idx[1] + dx[i]
                ny = idx[2] + dy[i]
                if nx < 0 or ny < 0 or nx >= n or ny >= n:
                    continue
                if data[nx][ny] == 0:
                    data[nx][ny] = data[idx[1]][idx[2]]
                    # 시간이 다 가기 전에 이미 원하는 위치에 바이러스가 퍼지면 바로 return
                    if data[x-1][y-1] != 0:
                        return data
                    # 새롭게 퍼진 바이러스 인덱스
                    virusIndex.append([data[nx][ny],nx,ny])
            # 기존에 있던(새로 추가된 바이러스 x) 바이러스가 모두 전염을 퍼뜨림  
            if pop_virus == count_virus:
                time+=1
                break   
    return data

print(spreadVirus(data)[x-1][y-1])