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

 

🎈 백준 18405 경쟁적 전염

www.acmicpc.net/problem/18405

18405번: 경쟁적 전염

 

❗ 문제의 핵심, 풀이 과정

• 바이러스는 1초마다 상하좌우 방향으로 증식해 나간다. 또한 어떤 특정 칸에 어떠한 바이러스가 존재하면, 그 곳에는 바이러스가 들어갈 수 없다.

=> 전형적인 bfs 문제이다. 초기 graph를 0으로 설정하고 바이러스가 있거나 번진 경우 graph를 그 바이러스로 변경시킨다.

 

• 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 

=> 처음 bfs를 진행할 때, 번호가 낮은 종류의 바이러스부터 큐에 넣고 시작해야 한다.

     - graph[i][j]와 i, j를 담은 배열을 정렬하여 큐에 넣는다.

 

• 시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.

=> 각 위치의 초를 저장할 second 리스트를 만들어 바이러스가 증식 할 때마다 초를 증가시킨다.

 

✅ 전체 코드

import sys
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split())

graph = [[0] * n for _ in range(n)]
second = [[0] * n for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
start = []

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

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

# 번호가 낮은 종류부터 증식, 큐에 낮은 번호부터 삽입하고 시작해야 한다
start.sort()
queue = deque(start)

while queue:
    virus, x, y = queue.popleft()

    if second[x][y] == s:
        break

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

        if nx < 0 or nx >= n or ny < 0 or ny >= n:
            continue

        if graph[nx][ny] == 0:
            graph[nx][ny] = virus
            second[nx][ny] = second[x][y] + 1
            queue.append((virus, nx, ny))

print(graph[target_x-1][target_y-1])