Q17. 백준 18405번 : 경쟁적 전염

띠리링구 2022. 2. 20. 08:04

18405번: 경쟁적 전염

첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치

www.acmicpc.net

전~형적인 bfs 문제이다.

다만 어렵게 풀면 정말 어려워질 수 있고 쉽게 풀면 정말 쉬워질 수 있는 무제

먼저 풀이 코드를 보자.

from collections import deque

#data input 부분
N, K = map(int, input().split())
data = []
virus_pos = []
for _ in range(N):
    data.append(list(map(int,input().split())))

    for i in range(N):
        if data[-1][i] != 0:
            virus_pos.append((data[-1][i], len(data)-1, i, 0))

S, X, Y = map(int, input().split())

#상하좌우 탐색을 편하게 하기 위한 배열
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

#바이러스 번호 순으로 오름차순 정렬해서 큐에 넣는다
virus = deque(sorted(virus_pos, key=lambda x: x[0]))

while virus:
    virus_num, row, col, timestep = virus.popleft()

    if timestep == S:
        break

    for i in range(4):
        newrow = row + dr[i]
        newcol = col + dc[i]

        if newrow >= 0 and newrow < N and newcol >= 0 and newcol < N and data[newrow][newcol]==0:
            data[newrow][newcol] = virus_num
            virus.append((virus_num, newrow, newcol, timestep+1))

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

굵은 글씨 친 부분이 핵심이다. 핵심은 두 가지.

1. 큐에 바이러스 정보를 넣을 때 timestep을 포함해서 넣는다.

2. 큐를 초기화 할 때 바이러스 정보를 오름차순 정렬해서 넣는다.

이 두 가지만 기억해도 어렵지 않게 문제를 풀 수 있다.