[BFS] 이코테 “경쟁적 전염” Python 풀이

문제

• NxN 크기의 시험관이 있다.
• 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다.
• 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.
• 시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다.
• 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다.
• 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.
• 시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오.
• 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.
• 이 때 X와 Y는 각각 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.
• 예를 들어 다음과 같이 3x3 크기의 시험관이 있다고 하자.
• 서로 다른 1번, 2번, 3번 바이러스가 각각 (1,1), (1,3), (3,1)에 위치해 있다.
• 이 때 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류를 계산해보자.

• 1초가 지난 후에 시험관의 상태는 다음과 같다.

• 2초가 지난 후에 시험관의 상태는 다음과 같다.

• 결과적으로 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류는 3번 바이러스다.
• 따라서 3을 출력하면 정답이다.

입력 조건

• 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000)
• 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다.
• 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다.
• 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다.
• 또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다.
• N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)

출력 조건

• S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력한다.
• 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.

입력 예시

3 3
1 0 2
0 0 0
3 0 0
2 3 2

3 3
1 0 2
0 0 0
3 0 0
1 2 2

출력 예시

3

0

풀이

• 바이러스는 낮은 번호부터 증식하므로, 초기 큐에, 번호가 낮은 바이러스부터 삽입하면 된다.

예제 코드

# https://www.acmicpc.net/problem/18405

import sys
from collections import deque

# 시험관 크기 및 바이러스 종류 저장
n, k = map(int, sys.stdin.readline().split())

# 바이러스 정보 저장
graph = []
# 바이러스의 추가 정보 저장
data = []

for i in range(n):
    graph.append(list(map(int, sys.stdin.readline().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)

# 결과를 위한 입력 [S초와 (X,Y)에 존재하는 바이러스의 종류]
s, x, y = map(int, sys.stdin.readline().split())

# 상하좌우 이동을 위한 좌표
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

while (q):

    # 현재 위치
    virus, time, i, j = q.popleft()

    # 현재 위치의 바이러스가 S초까지 확산된 바이러스라면 종료
    if (time == s):
        break

    # 상하좌우로 바이러스 확산
    for l in range(4):
        nx = i + dx[l]
        ny = j + dy[l]
        # 해당 위치로 확산될 수 있을 경우
        if (0<= nx and nx < n and 0 <= ny and ny < n and graph[nx][ny] == 0):
            # 그래프에 바이러스 확산 표시
            graph[nx][ny] = virus
            # 큐에 삽입
            q.append((virus, time+1, nx, ny))

print(graph[x-1][y-1])

참고

• 이것이 취업을 위한 코딩 테스트다. with python