[Python/Baekjoon] 18405. 경쟁적 전염

💬 문제

문제 난이도: 백준 골드 5

문제 링크: https://www.acmicpc.net/problem/18405

❗️접근 방법

• 최소 시간, 최단 거리를 묻는 문제가 아니므로 bfs로 풀 필요가 없다고 생각했다.
• 완전 탐색을 하면서 바이러스가 전염되지 않은 곳 사방(동서남북)에 하나라도 바이러스가 있고, 둘 이상이라면 그 최솟값과 좌표 정보를 바탕으로 갱신한다.

✅ 정답 코드

# 경쟁적 전염 #0이 아니라 1부터 시작하는 것임(X, Y에 유의하기)
import sys
input = sys.stdin.readline
print = sys.stdout.write

N, K = map(int, input().split(' '))
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split(' '))))
S, X, Y = map(int, input().split(' '))
visited = [[-1]*(N) for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def defaultCondition():
    willVirusSet = set()
    cnt = 0
    for x in range(N):
        for y in range(N):
            nn = K+1
            if graph[x][y] == 0:
                cnt += 1
                for i in range(4):
                    nx = x+dx[i]
                    ny = y+dy[i]
                    if 0<=nx<N and 0<=ny<N and graph[nx][ny] > 0:
                        nn = min(nn, graph[nx][ny])
            if nn != K+1:
                willVirusSet.add((nn, x, y))
    return cnt, willVirusSet

def solution():
    minute = 0
    while minute < S:
        minute += 1
        cnt, willVirusSet = defaultCondition()
        if cnt <= 0:
            break
        for n, x, y in willVirusSet:
            graph[x][y] = n
    return str(graph[X-1][Y-1])

print(solution())

✍️ 유의해야할 부분

• '인접한 가장 작은 번호의 바이러스로 전염된다'라는 조건이 마치 minHeap을 사용해야 하는 것처럼 보이지만
• 그렇게 되면 heap에 불필요한 정보를 저장하게 된다.
• 가령, 인접한 바이러스가 1, 2로 2개 이상이라고 하자.
• 이때 결과적으로 1로만 전염이 될 것이기 때문에 2에 대한 정보는 저장할 필요가 없다.
• 따라서 현재는 바이러스에 감염되지 않았고, 인접한 바이러스가 1개 이상이라면 가장 작은 바이러스 번호만을 현재의 좌표와 함께 저장하고 갱신하면 된다.