[백준 18405번 -경쟁적 전염]-파이썬

백준 18405번 파이썬 풀이

<문제>

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

18405번: 경쟁적 전염

<풀이>

바이러스의 정보를 담을 리스트(data)에 바이러스의 종류,위치,시간을 입력한다.

바이러스는 항상 낮은번호부터 확산한다 했으므로 data를 오름차순 정렬한다.

data를 큐에 넣은후 BFS알고리즘을 적용한다.

 

-BFS알고리즘 설명-

1. 시간(s)가 목표한 시간(target_s)에 도달하면 while문을 멈춘다.

2. 큐에서 원소를 꺼낸후 네 방향중 바이러스가 이동 가능한위치로 바이러스를 확산시킨다.

3. 바이러스를 확산시킨후 1초지난시간을 반영(s+1)하여 (바이러스의 번호,시간,위치)를 큐에 삽입한다.

4.위 2~3번과정을 1번을 만족하거나 큐가 빌때까지 반복한다.

<코드>-파이썬

import sys
from collections import deque
n,k = map(int,sys.stdin.readline().split())
graph = []
data = []
for _ in range(n):
    graph.append(list(map(int,sys.stdin.readline().split())))
for i in range(n):
    for j in range(n):
        if graph[i][j]!=0:
            data.append((graph[i][j],0,i,j))
data.sort()
q = deque(data)

target_s,target_x,target_y = map(int,sys.stdin.readline().split())
dx = [-1,0,1,0]
dy = [0,-1,0,1]
while q:
    virus,s,x,y = q.popleft()
    if s == target_s:
        break
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if nx>=0 and nx<n and ny>=0 and ny<n:
            if graph[nx][ny] == 0:
                graph[nx][ny] = virus
                q.append((virus,s+1,nx,ny))
print(graph[target_x-1][target_y-1])