[BFS] 백준 18405번 '경쟁적 전염' (Python)

<문제 링크>

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

18405번: 경쟁적 전염

---

<문제 풀이>

1. 차례대로 바이러스를 퍼트려야 하므로 deque 사용

2. 바이러스 종류, 시간(s), x, y 값을 q에 담음

3. q가 있을 때, 시간이 지날 때까지 반복

4. q 순서대로 상하좌우 바이러스 증식

 

<코드>

#220328 실패
n,k = map(int,input().split())
graph = []
for i in range(n):
    graph.append(list(map(int,input().split())))
s,x,y = map(int,input().split())

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

virus = {v:set() for v in range(1,k+1)}
for i in range(s):
    for kk in range(1,k+1):
        for xx in range(n):
            for yy in range(n):
                if graph[xx][yy] == kk:
                    virus[kk].add((xx,yy))
    for key, value in virus.items():
        for vx,vy in value:
            for d in range(4):
                nx = vx+dx[d]
                ny = vy+dy[d]
                if nx >= 0 and ny >= 0 and nx < n and ny < n:
                    if graph[nx][ny]==0:
                        graph[nx][ny] = key

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

#이취코 답
from collections import deque

n,k = map(int,input().split())
graph = []
data = []

for i in range(n):
    graph.append(list(map(int,input().split())))
    for j in range(n):
    	if graph[i][j] != 0:
        	data.append((graph[i][j],0,i,j))
            
data.sort()
q = deque(data)
s,x,y = map(int,input().split())

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

while q:
	virus, ss, xx, yy = q.popleft()
    if ss == s:
    	break
    for d in range(4):
        nx = xx+dx[d]
        ny = yy+dy[d]
        if nx >= 0 and ny >= 0 and nx < n and ny < n:
            if graph[nx][ny]==0:
                graph[nx][ny] = virus
                q.append((virus, ss+1, nx,ny))

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

 

<고쳐야 할 점>

• 복습 알고리즘
• deque 사용
• 바이러스 종류, 시간, x, y 같이 q에 담음