[Algorithm] 백준 18405 경쟁적 전염 | 파이썬 BFS

※ 18405 경쟁적 전염

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

첫번째 문제 풀이 (시간 초과)

문제를 보고 먼저 생각해낸 해결방법은

1. 바이러스 번호 1번부터 graph에서 위치한 자리값을 position 배열에 저장한다.

2. position 배열에서 하나씩 꺼내어 확산을 진행한다.

N, K = map(int,input().split())
graph = []
for i in range(N):
    graph.append(list(map(int,input().split())))
S, X, Y = map(int,input().split())
#graph = [[1, 0, 2], [0, 0, 0], [3, 0, 0]]

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

def bfs(x,y,num):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= N or ny >= N:
            continue
        if graph[nx][ny] == 0:
            graph[nx][ny] = num

for _ in range(S):
    position = []
    for i in range(N):
        for j in range(N):
            if graph[i][j] != 0:
                position.append((i,j,graph[i][j]))
    #position = [[0,0,1],[0,2,2],[2,0,3]]
    #position = [(0, 0, 1), (0, 1, 2), (0, 2, 2), (1, 0, 3), (1, 2, 2), (2, 0, 3), (2, 1, 3)]
    for i in range(1,len(position)):
        x,y,num = position[i]
        bfs(x,y,num)
#graph = [[1, 1, 2], [1, 1, 2], [3, 3, 2]]
print(graph[X-1][Y-1])

아무래도 중복연산도 많고 모든 좌표를 탐색하는 과정에서 복잡도가 깊어지는 문제가 있는 것 같다.

 

문제 해결 TIP

기존 확산 문제들과 다르게 0이라고 해서 계속 퍼뜨리는 것이 아닌, 바이러스 번호 1번부터 상하좌우 한번씩 퍼뜨린 후 다음 바이러스 번호로 넘어가야 한다. 따라서 큐에 바이러스 번호, 시간, 위치 좌표를 함께 저장하여 BFS를 실행하는 것이 효과적이다. 진행하는 동안 큐는 다음과 같이 삽입된다.

 

전체 코드

from collections import deque

N, K = map(int,input().split())
graph = []
data = []
for i in range(N):
    graph.append(list(map(int,input().split())))
    # graph = [[1, 0, 2], [0, 0, 0], [3, 0, 0]]
    for j in range(N):
        if graph[i][j] != 0:
            #바이러스 번호, 시간, 위치
            data.append((graph[i][j],0,i,j))
S, X, Y = map(int,input().split())

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

data.sort()
#data = [(1, 0, 0, 0), (2, 0, 0, 2), (3, 0, 2, 0)]
q = deque(data)
while q:
    num,s,x,y = q.popleft()
    if s == S:
        break
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx and nx < N and 0 <= ny and ny < N:
            if graph[nx][ny] == 0:
                graph[nx][ny] = num
                q.append((num,s+1,nx,ny))
#graph = [[1, 1, 2], [1, 1, 2], [3, 3, 2]]
print(graph[X-1][Y-1])