백준 18405번 - 경쟁적 전염

경쟁적 전염 문제 바로 가기

풀이 날짜: 2026-01-08

baekjoon 알고리즘 문제 풀이

풀이 코드

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

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

n,k = map(int, input().split())
graph = []
data = []

for i in range(n):
    graph.append(list(map(int, input().split())))
    for j in range(n):
        if graph[i][j] != 0:
            data.append((graph[i][j],0,i,j)) #바이러스 종류, 시간, 위치x, 위치y

data.sort()
q = deque(data)

targetS,targetX,targetY = map(int, input().split())

while q:
    virus,s,x,y = q.popleft()
    if s == targetS:
        break

    for i in range(4):
        nx = dx[i] + x
        ny = dy[i] + y
        if 0<=nx<n and 0<=ny<n and graph[nx][ny] == 0:
            graph[nx][ny] = virus
            q.append((virus,s+1,nx,ny))

print(graph[targetX-1][targetY-1])
  

문제 핵심 요약:

단순 BFS가 아닌, 바이러스 번호가 작은 것이 항상 먼저 퍼져야 한다는 조건을 기억해두자.

• 초기 바이러스들을 번호 기준으로 정렬해서 큐에 넣기
• 큐에는 (virus,time,x,y) 형태로 넣고 BFS
• BFS는 time이 증가하면서 퍼지고
• 같은 time 안에서는 큐에 들어간 순서가 유지되므로, 정렬한 순서가 그대로 우선순위를 만든다.

내가 선택한 풀이 방식

1) 입력에서 ‘초기 바이러스 위치’를 모두 수집

• 처음부터 여러 종류의 바이러스가 동시에 존재하므로, BFS의 시작점이 1개가 아니라 여러 개다.
• 따라서 그 시작점들을 정렬해서 큐에 넣는 게 핵심이다.

2) 번호 순서 보장을 위해 초기 목록을 정렬

• 정렬을 하면 virus 번호가 오름차순으로 들어가므로 0초에 퍼질 순서가 정확해진다.
• BFS가 진행될 때도 “1초에 새로 감염된 것들”은 큐 뒤로 들어가면서 같은 시간대 내에서도 번호 우선이 유지된다.

시간 관리 방식

• 일반 BFS는 “level”로 시간을 관리할 수도 있지만 이 코드는 튜플에 s를 넣어서 명시적으로 관리했다.
• q.append((virus, s+1, nx, ny))

break로 조기 종료

• BFS 특성상 큐에서 꺼내는 순서는 시간이 증가하는 방향
• 처음으로 targetS 시간에 도달한 순간 이후는 의미가 없다.

(X,Y) 1-index → 0-index 변환

• 출력에서 -1 빠뜨리면 바로 틀림.