백준: 18405 경쟁적 감염

문제

18405번: 경쟁적 전염

 

문제 풀이

 NxN에 시험관에 바이러스들이 있을 때, 바이러스의 종류는 1부터 K까지 존재한다. 이때, 1번 바이러스부터 우선적으로 전염될 때, S초에 X, Y에 전염된 바이러스의 종류를 출력하는 문제이다. 초기에 전염되지 않은 곳은 0, 바이러스가 있는 곳은 1 ~ K 사이의 수로 표시된다.

 

• BFS를 통해 탐색하여 문제를 풀 수 있다.
• 최초에 주어진 시험관에서 바이러스의 종류를 찾고, 좌표를 기록한다.
  • 1번 바이러스 부터 전염되어어야 하므로 찾은 바이러스를 정렬하여 `deque`에 삽입한다.
• 상, 하, 좌, 우로 탐색하여 전염시킨다.
• 전염을 진행하며, 시간이 S가 되는 경우 전염을 중단시킨다.

 

코드

from sys import stdin
from collections import deque


def visitable(x, y):
    return 0 <= x < n and 0 <= y < n and not graph[x][y]


def bfs(start):
    q = deque(start)
    dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))

    while q:
        cur_virus, x, y, time = q.popleft()

        if time == target[S]:
            break

        for dx, dy in dirs:
            next_x, next_y = x + dx, y + dy

            if visitable(next_x, next_y):
                graph[next_x][next_y] = cur_virus
                q.append((cur_virus, next_x, next_y, time + 1))


if __name__ == '__main__':
    S, X, Y = 0, 1, 2
    n, k = map(int, stdin.readline().split())
    graph = [list(map(int, stdin.readline().split())) for _ in range(n)]
    target = list(map(int, stdin.readline().split()))
    virus = []

    for i in range(n):
        for j in range(n):
            if graph[i][j] != 0:
                virus.append([graph[i][j], i, j, 0])

    bfs(sorted(virus))

    print(graph[target[X] - 1][target[Y] - 1])