[백준] 18405 파이썬(python) : 경쟁적 전염 - (★)

18405번: 경쟁적 전염

 

 

import sys
from collections import deque
n, k = map(int, sys.stdin.readline().split())
graph = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ] #1
data = []
s, end_x, end_y = map(int, sys.stdin.readline().split()) #2
dx = [ 0, 0, -1, 1 ]
dy = [ -1, 1, 0, 0 ]
for i in range(n):
    for j in range(n):
        if graph[i][j] != 0: #3
            data.append((graph[i][j], i, j, 0))
data.sort() #4
q = deque(data) #5
def bfs():
    while q:
        value, x, y, time = q.popleft()
        if time == s: #6
            return
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if graph[nx][ny] == 0:
                    graph[nx][ny] = value
                    q.append((value, nx, ny, time+1)) #7
bfs()
print(graph[end_x-1][end_y-1]) #8

 

#1 : 그래프 입력값 받아줌

#2 : 시간과 마지막 위치 입력

#3 : graph를 돌면서 0이 아닌 부분(바이러스가 있는 부분)은 바이러스의 "값"과 "위치" 그리고 "시간"을 data리스트에 저장

#4 : "번호가 낮은 순서의 바이러스부터 순서대로 증식"한다는 조건이 있음

#5 : 데크에 data리스트를 삽입

#6 : 만일 time이 s와 같으면 리턴

#7 : 방향벡터로 주위를 탐색했을때 위의 조건이 성립하면 q에 바이러스의 값과 위치 그리고 시간+1을 추가

#8 : 첫번째 칸을 (1,1)으로 했는데 (0, 0)이 처음칸이니까 원하는 위치에서 -1한 위치의 값을 출력

 

---

7576번: 토마토