경쟁적 전염

 

문제

1부터 K까지 번호가 있는 바이러스가 K 있을 때,

N크기의 맵에서 바이러스가 증식한다.

 

유형

- 일종의 퍼진다 개념이다.

- 노드와 간선의 개념이다.

- 그래프에서 연결된 노드 집합 구하는 것과 유사하다.

 

구현

- 입력을 받을때, 바이러스 초기시간(0초), 위치, 값을 처리한다.

- 이 후, 값을 작은 순서대로 정렬한다. -> 번호가 작은 순서대로 증식하기 때문에

- 큐에 넣는다.

- 선입부터 쭉쭉 꺼낸다.

- 만약 꺼낸 데이터의 시간이 기준 시간보다 같다면 멈춘다.

- 꺼낸 데이터를 상하좌우 따져서 범위 안인지 확인한다.

- 범위 안이면 숫자로 방문처리, 큐에 삽입, (삽입시 현재 시간 + 1 해야한다.)

 

 

코드

from collections import deque

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))

data.sort()
q = deque(data)

target_s, target_x, targer_y = map(int, input().split())

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

while q:
    virus, s, x, y = q.popleft()
    if s == target_s:
        break
    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
                q.append((virus, s+1, nx, ny))

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