18405번 경쟁적전염

문제

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

접근방식

처음에는 번호별로 따로 큐를 관리하는 식으로 구현했는데 하다보니 하나의 번호가 여러군데 등장하는 경우 등, 복잡하고 고려해질 게 많아서 큐에다가 레벨 정보를 함께 넣는 식으로 해결하기로 했다.

👉 레벨? BFS에서 가장 중요한 개념이라고도 볼 수 있는데, pop 한 요소에 대해 다음 가능한 요소들을 append 할 때 레벨이 하나 더해진다.

레벨을 이용하면 초당 변화를 관리할 수 있다. 만약 레벨 + 1이 제시된 초 이하일 때만 append 할 수 있도록 구현했다.

중간에 각 초당 matrix를 변화시키는 데서 헤맨 건 안 비밀

결국, 큐에다가 [번호, x, y, 레벨] 이렇게 넣어서 관리했다. 처음에 정렬하고 시작했다.

코드

from collections import deque

def solution(n, matrix, s, x, y):
    lst = list()
    for i in range(n):
        for j in range(n):
            if matrix[i][j] > 0:
                lst.append([matrix[i][j], i, j, 0]) 
    lst.sort()
    queue = deque(lst)
    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    while queue:
        v, cx, cy, d = queue.popleft()
        if d + 1 <= s:
            for dx, dy in dirs:
                if 0 <= cx + dx < n and 0 <= cy + dy < n and matrix[cx+dx][cy+dy] == 0:
                    queue.append([v, cx+dx, cy+dy, d + 1])
                    matrix[cx+dx][cy+dy] = v
    return matrix[x-1][y-1]

n, k = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
s, x, y = map(int, input().split())
print(solution(n, matrix, s, x, y))