https://www.acmicpc.net/problem/18405
NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.
시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.
시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.
입력
첫째 줄에 자연수 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을 출력한다.
# 18405 경쟁적 전염
# 상 하 좌 우
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
N, K = map(int, input().split())
blocks = [list(map(int, input().split())) for _ in range(N)]
S, X, Y = map(int, input().split())
queue = list()
for r in range(N):
for c in range(N):
if blocks[r][c] != 0:
queue.append([blocks[r][c], r, c])
queue.sort()
temp_queue = queue[:]
for _ in range(S):
queue = list()
while temp_queue:
c_block, p_r, p_c = temp_queue.pop(0)
for k in range(4):
cr = p_r + dr[k]
cc = p_c + dc[k]
if 0 <= cr and cr < N and 0 <= cc and cc < N and blocks[cr][cc] == 0:
blocks[cr][cc] = c_block
queue.append([blocks[cr][cc], cr, cc])
temp_queue = queue[:]
print(blocks[X - 1][Y - 1])
구현 문제였다.
특이한 사항은
- queue 안의 blocks[r][c] 값을 먼저 정렬해줘야 하는 점과,
- queue, temp_queue를 따로 나눈 뒤, temp_queue로 BFS를 1초에 단 한 칸씩 돌리는 점이다.
이중리스트의 복사를 [:] 연산을 이용하여 쉽게 구현할 수 있었다.
코드를 짠 뒤 한 번에 정답을 맞춰 다소 당황했다.
