🔗 Problem Link

 

18405번: 경쟁적 전염

첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치

www.acmicpc.net


❔Thinking

  • NXN 시험관에 바이러스가 순서대로 상,하,좌,우로 퍼져나갈 때, S초 뒤에 X,Y에 존재하는 바이러스를 반환한다.
  • 바이러스는 1~K까지 있고, 작은 순서대로 퍼져간다.

💻Solution

import heapq
import sys

input = sys.stdin.readline

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

n, k = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))
s, x, y = map(int, input().split())

# 초기 바이러스 확인
q = []
for i in range(n):
    for j in range(n):
        if graph[i][j] != 0:
            heapq.heappush(q, (graph[i][j], i, j))

# 바이러스 감염
def virus_spread(graph, q):
    next_q = []
    while q:
        virus, x, y = heapq.heappop(q)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<len(graph) and 0<=ny<len(graph[0]) and graph[nx][ny] == 0:
                graph[nx][ny] = virus
                heapq.heappush(next_q, (virus, nx, ny))
    return graph, next_q

# s초 후 상태
for t in range(s):
    graph, q = virus_spread(graph, q)
    
print(graph[x-1][y-1])

🗝️keypoint

  1. 바이러스가 작은 순서대로 퍼져나가므로, 그 순서를 유지하는 것이 중요하다.
  2. 바이러스는 초당 상,하,좌,우 각 한 번씩만 퍼져나간다.

'코딩테스트 > Python' 카테고리의 다른 글

[Baekjoon] 6497. 전력난  (0) 2023.01.08
[Baekjoon] 14501. 퇴사  (0) 2023.01.08
[Programmers] Level 2. 문자열 압축  (0) 2023.01.05
[Baekjoon] 1932. 정수 삼각형  (0) 2023.01.03
[Baekjoon] 18352. 특정 거리의 도시 찾기  (0) 2022.12.29

+ Recent posts