[백준] 경쟁적 전염

출처:: https://www.acmicpc.net/problem/18405

분류::  bfs

 

1. 문제 이해 및 해결과정

- 바이러스가 낮은 번호부터 증식한다 ->큐에 낮은 바이러스 번호부터 넣어야한다.

 

2. 풀이방법

  1. [ python ] bfs

#경쟁적 전염
#https://www.acmicpc.net/problem/18405
import sys
from collections import deque
sys.stdin = open("input.txt","r")
input=sys.stdin.readline
n,k=map(int,input().split())
board=[list(map(int,input().split())) for i in range(n)]
virus=[] #바이러스에 대한 정보
dh=[-1,1,0,0]
dw=[0,0,-1,1]
s,x,y =map(int,input().split()) #제한시간, 좌표

def bfs():
    while q:
        v,t,curh,curw=q.popleft() #바이러스번호,시간,위치
        if s==t: #주어진 시간이되면
            break
        for i in range(4):
            nh=curh+dh[i]
            nw=curw+dw[i]
            if 0<=nh<n and 0<=nw<n and board[nh][nw]==0: #아직 방문안했으면
                board[nh][nw]=v
                q.append((v,t+1,nh,nw)) #바이러스번호, 시간 +1, 좌표


#출발좌표 큐에 다 넣고 시작
for i in range(n):
    for j in range(n):
        if board[i][j]>0: #바이러스가 있으면
            virus.append((board[i][j],0,i,j))

virus.sort() #바이러스가 낮은 번호부터 증식하므로
# print(virus)
q=deque(virus)
bfs()

# for i in range(n):
#     print(board[i])

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

 

3. 오답원인

 

4. 알게된 점

 - bfs중에 큐에 넣기전에 sort하는 과정이 특이했다.