[BFS] - G5_18405_경쟁적 전염

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

18405번: 경쟁적 전염

 

 

해당 문제는 전에 푼 토마토 문제와 매우 유사하다. 

 

본인이 푼 해결 방식은 이러하다

 

- 이 문제는 결국 낮은 숫자의 바이러스들부터 큰 숫자의 바이러스들까지 순서대로 퍼지게 만드는 것이 요점인데 순서를 정렬하기 위해 힙큐를 써서 해결을 했다.

 

 

 

1.  for 문으로 전체 배열을 돌면서 0이 아닌 바이러스들을 힙큐에 넣는다.
2. 1초마다 BFS로 힙큐를 비우면서 인접한 배열의 정보를 다시 다른 힙큐에 넣는다.
3. 첫번째 힙큐가 비었을 때, 나머지 힙큐에 있던 수들을 다시 첫번째 힙큐에 넣어준다.

📌 - 첫번째 방식으로 푼 코드

from sys import stdin as s
from collections import deque
import heapq

s = open('input.txt','rt')

N , K = map(int,s.readline().split())

arr = [list(map(int,s.readline().split())) for _ in range(N)]

S, X ,Y = map(int,s.readline().split())

visited = [[False] * N for _ in range(N)]

queue = []
nextQueue = []

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



def BFS():

    while queue:
        number, x, y, time = heapq.heappop(queue)
        if time > S:
            break

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N and not visited[nx][ny] and time < S:
                heapq.heappush(nextQueue,(number,nx,ny,time+1))
                arr[nx][ny] = number
                visited[nx][ny] = True

        
        if not queue:
            while nextQueue:
                heapq.heappush(queue,heapq.heappop(nextQueue))



for i in range(N):
    for j in range(N):
        if arr[i][j] != 0:
            visited[i][j] = True
            heapq.heappush(queue,(arr[i][j],i,j,0))


BFS()

print(arr[X-1][Y-1])

 

 

이렇게 해도 정답이 나오긴 한다. 하지만 굳이 이렇게 힙큐를 쓰지 않고도 문제를 해결할 수 있다.

 

힙큐로 순서를 정렬하지 말고 처음 넣을때부터 정렬을 해주면 더 간단하게 코드를 만들 수 있다.

 

📌 - 두 번째 방식

 

from sys import stdin as s
from collections import deque
import heapq

s = open('input.txt','rt')

N , K = map(int,s.readline().split())

arr = [list(map(int,s.readline().split())) for _ in range(N)]

S, X ,Y = map(int,s.readline().split())

visited = [[False] * N for _ in range(N)]

queue = deque()

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



def BFS():

    while queue:
        number,x,y ,time = queue.popleft()
        if time > S:
            break

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N and not visited[nx][ny] and time < S:
                queue.append((number,nx,ny,time+1))
                arr[nx][ny] = number
                visited[nx][ny] = True


temp = []


for i in range(N):
    for j in range(N):
        if arr[i][j] != 0:
            visited[i][j] = True
            temp.append((arr[i][j],i,j,0))
            


temp.sort()
for i in temp:
    queue.append((i[0],i[1],i[2],0))


BFS()

print(arr[X-1][Y-1])

코드 리뷰 중 다른 동기가 알려줘서 더 간단하게 해결할 수 있음을 알게되었다.