[백준] 바이러스 공격 31791번 우선순위 큐 (python)

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

풀이 방법

일반적인 bfs 문제에서 퍼질 수 있는 시간이 정해진 문제이다.

바이러스의 시간이 많은 것부터 처리하기 위해 map heap의 우선순위 큐를 사용했다. 

그러기 위해 남은 시간을 음수로 하여 저장했다.

그 후 시간이 많이 남은 바이러스 부터 전파를 시작해 빈 곳이면 시간 - 1을 우선순위 큐에 넣어주고

만약 건물이라면 남은 바이러스 시간 - 건물 전파시간 - 1을 해주어서 이 수가 만약 양수이면 건물이 감염된 것이고 음수이면 건물이 감염이 안 된 것으로 처리했다. 그 후 계산한 값을 우선순위 큐에 넣어주었다.

 

bfs를 탐색하며 우선순위 큐에서 값을 꺼내어 남은 시간이 양수이면 전파를 시작했고 0 이하라면 전파를 멈췄다.  

 

전체 코드

import heapq

N, M = map(int, input().split())
TG, TB, X, B = map(int, input().split())

school = [[0 for _ in range(M)] for _ in range(N)]
visited = [[0 for _ in range(M)] for _ in range(N)]
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

def bfs():
    while len(q) != 0:
        life, y, x = heapq.heappop(q) ## 바이러스 남은 시간, y좌표, x좌표
        life = -life ## 바이러스 전파 가능한 시간 양수로 (우선순위 큐에서 꺼냄)
        if life > 0: ## 바이러스전파 가능시간이 남았으면 전파 시작  
            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]
                if 0 <= ny < N and 0 <= nx < M:
                    if visited[ny][nx] == 0:
                        visited[ny][nx] = 1
                        if school[ny][nx] == 0: ## 빈 곳이면 
                            heapq.heappush(q, [-(life - 1), ny, nx]) ## 시간 -1 한 값 저장
                            school[ny][nx] = -1 ## 오염 표시 
                        else:
                            heapq.heappush(q, [-(life - school[ny][nx]-1), ny, nx]) ## 바이러스 가능 시간 - 건물의 안전 시간
                            school[ny][nx] = -(life - school[ny][nx]) ## 양수이면 안전 음수이면 오염 

q = []
for i in range(N):
    temp = input()
    for j in range(M):
        if temp[j] == '.': ## 빈 곳
            school[i][j] = 0
        elif temp[j] == '*': ## 바이러스 시작 
            school[i][j] = -TG
            heapq.heappush(q, [-TG, i, j]) ## 맥스힙을 사용하기 위해 -부호로 heap에 추가
            visited[i][j] = 1
        else: ## 건물이 있는 곳 
            school[i][j] = TB

bfs()

flag = 0
for i in range(N):
    for j in range(M):
        if school[i][j] >= 0: ## 오염이 안된 곳
            flag = 1 ## 전멸이 아님
            print(i+1, j+1)

if flag == 0: ## 전멸
    print(-1)