경쟁적 전염

📌문제

NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나눠지며, 특정한 위치에 바이러스가 존재할 수 있다. 바이러스의 종류는 1~K번까지 K가지가 있으며, 모든 바이러스는 이 중 하나에 속한다.

모든 바이러스는 1초마다 상 하 좌 우의 방향으로 증식하는데 매초 번호가 낮은 종류의 바이러스부터 먼저 증식한다.

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

 

📌풀이

너비우선탐색(BFS) 이용

낮은 번호부터 증식하므로 초기에 큐에 원소를 삽입할 때 정렬해서 낮은 바이러스의 번호부터 삽입

 

📌코드

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:
            # (바이러스 종류, 시간, X, Y) 삽입
            data.append((graph[i][j], 0, i, j))

# 정렬 이후에 큐로 옮기기(낮은 번호의 바이러스가 먼저 증식)
data.sort()
q = deque(data)

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

# 바이러스가 퍼질수 있는 4가지 위치
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 너비 우선 탐색(BFS)
while q:
    virus, s, x, y = q.popleft()
    if s == target_s:
        break
    # 현재 노드에서 주변 4가지 위치를 확인
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 해당 위치로 이동할 수 있는 경우
        if 0 <= nx and nx < n and 0 <= ny and ny < n:
            # 아직 방문하지 않은 위치라면 그 위치에 바이러스 넣기
            if graph[nx][ny] == 0:
                graph[nx][ny] = virus
                q.append((virus, s + 1, nx, ny))

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

 

📌참고

https://g.co/kgs/eyd5SSd

이것이 취업을 위한 코딩 테스트다 with 파이썬