백준 18405 | 경쟁적 전염 (BFS)

문제 출처 : https://www.acmicpc.net/problem/18405

문제

• n x n 크기 시험관가 있다.
• 시험관은 1 x 1 크기의 칸으로 나뉘어져있다.
• 특정한 위치에는 바이러스가 존재할 수 있다.
• 모든 바이러스는 1번부터 k번까지의 바이러스 종류 중 하나에 속한다.
• 모든 바이러스는 1초마다 상하좌우의 방향으로 증식한다
• 매초마다 낮은 종류의 바이러스부터 먼저 증식한다.
• 증식과정에서 특정 칸에 이미 바이러스가 존재한다면 그곳에는 다른 바이러스가 들어갈 수 없다
• 시험관 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후 (x, y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오
• 만약 s초가 지난 후 해당 위치에 바이러스가 존재하지 않는다면 0 출력하시오.

문제 접근 방법

• 같은 시간에 여러개의 바이러스가 있다면 번호가 낮은 바이러스부터 증식을 해야하므로 처음에는 우선순위 큐를 이용하여 BFS 탐색을 진행하려 했었다.
  • 하지만 우선순위 큐를 사용하면
    • 바이러스가 낮은 바이러스만 계속 우선적으로 탐색하여 번호가 높은 다른 바이러스들은 증식하지 못하게 되어 다른 처리가 필요해보였다.
  • 따라서 초기에 큐 에 (바이러스 번호, 행 좌표, 열 좌표, 시간 (초기 : 0)를 추가하고
    • 바이러스 번호를 기준으로 오름차순으로 정렬(sort)하여 번호가 낮은 바이러스부터 상하좌우로 한 칸씩 증식하도록 했다.
• 바이러스의 증식을 BFS 탐색 하면서 시간(s)의 처리를 어떻게 해야할까 고민했다.
  • s 초가 지난 후의 (x, y) 에 존재하는 바이러스의 종류를 찾기 위해서
    • 큐에 시간 정보도 같이 삽입하여 s 초가 지나면 BFS 탐색을 중단하도록 했다.
    • 만약 시간이 다 되기전에 시험관이 모두 바이러스에의해 증식되었다면 목표 지점의 바이러스 번호를 반환했다.

코드

import sys
import heapq
from collections import deque

input = sys.stdin.readline

# 문제 입력값 저장
n, k = map(int, input().split())
graph = []
visited = []

for i in range(1, n + 1):
    graph.append(list(map(int, input().split())))

s, target_x, target_y = map(int, input().split())

# print(n, k)
# print(graph)
# print(f'{s}초 후 {target_x}행, {target_y}열의 바이러스 번호는 ?)

queue = []

# 큐에 ( 바이러스 번호, 행, 열, 시간(초기 : 0) ) 저장
for i in range(n):
    for j in range(n):
        if graph[i][j]: 
            queue.append( (graph[i][j], i, j, 0) )

# 바이러스가 1번부터 퍼져야하므로 오름차순 정렬 후 deque 생성
queue.sort()
queue = deque(queue)

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

def bfs():
    while queue:
        virus_num, x, y, time = queue.popleft()

        # s초가 지나면 목표 지점 바이러스 번호 반환
        if time == s:
            return(graph[target_x - 1][target_y - 1])

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 해당 위치가 시험관 안이고 다른 바이러스가 없다면
            if 0 <= nx < n and 0 <= ny < n:
                if graph[nx][ny] == 0:
                    graph[nx][ny] = virus_num
                    # 다음 위치를 큐에 넣고 시간 + 1
                    queue.append((graph[x][y], nx, ny, time + 1))

    # 시간이 다 되기 전에 큐가 빈다면 목표 지점 바이러스 번호 반환
    return graph[target_x - 1][target_y - 1]

print(bfs())