Q17. 경쟁적 전염
🐣문제
NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.
시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.
시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.
🐥풀이
16번 연구소 문제랑 거의 유사한 문제이다.
다만 연구소는 번식할 수 있을만큼 증식하고, 경쟁적 전염은 일정 시간 동안만 증식한다.
그럼 연구소 문제와 똑같이 큐를 사용해보자.
먼저, 입력값을 받을 때 바이러스 정보(위치, 번호)를 큐(리스트)로 받아온다.
그리고 s초 동안 증식시키자.
여기서 주의할 점은, 1초동안 증식 전에 큐에 들어있던 바이러스만 증식하는 것이다. 또한, 바이러스 번호가 낮은 순으로 증식한다.
그럼 1초동안 아래와 같은 과정을 거쳐 바이러스는 증식한다.
번호 순으로 증식하니까, 큐를 바이러스 번호 기준으로 오름차순 정렬해야 한다.
그리고 현재 큐에 들어있는 바이러스만 증식하므로, 현재 큐의 길이만큼만 증식시키도록 한다.
위와 같이 제한을 걸었으면,
큐에서 바이러스 정보를 하나씩 꺼낸다. 위치 정보에 대하여 상하좌우로 시험관 내부이고 빈값이면 증식시킨다. 시험관 배열 해당 위치에 바이러스 번호 값을 저장하고, 바이러스 큐에 증식한 바이러스의 위치와 번호 정보를 추가한다. 그럼 증식 끝.
이 과정을 s초, 즉 s번 반복한다.
s초가 끝난 후, 시험관에서 해당 위치의 값 (바이러스 번호)을 출력한다.
🐓코드
import sys
input = sys.stdin.readline
n, k = map(int, input().split()) # 시험관, 바이러스 최대번호
table = [] # 바이러스 정보
board = [] # 시험관
for i in range(n):
virus = list(map(int, input().split()))
board.append(virus)
for j in range(len(virus)):
if virus[j]!=0:
table.append([i,j,virus[j]]) # 바이러스 위치, 바이러스 번호
s, x, y = map(int, input().split()) # 시간, x좌표, y좌표
dist = [[-1,0],[1,0],[0,1],[0,-1]]
# s초동안 증식
for _ in range(s):
table = sorted(table, key=lambda x:x[2]) # 바이러스 번호 작은 것부터 정렬
length, count = len(table), 0
# 증식하기 전의 바이러스만 증식함 (1초동안)
while count<length:
# 바이러스 위치, 번호
vx, vy, v = table.pop(0)
for d in dist:
dx, dy = vx+d[0], vy+d[1]
# 상하좌우가 시험관 내부이고 빈칸이면 증식
if 0<=dx<n and 0<=dy<n and board[dx][dy]==0:
board[dx][dy] = v
table.append([dx,dy,v])
# 전부터 있던 바이러스 하나 증식
count += 1
# 해당 위치의 바이러스 번호 출력
print(board[x-1][y-1])⭐2022.04.13
연구실 문제 풀고 전보다 수월하게 푼 문제 :) BFS나 DFS 유형은 비슷한 거 같으니 잘 공부해놓고 관련 문제들도 열심히 풀어봐야겠다!
