☁️ 문제

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

(0,0)에서 시작해서 (n-1,n-1)까지 가는데 그래프에서 검은 방을 최소한으로 지나서 목적지까지 도착해야하는 문제이다.

(0,0)에서 탐색을 시작하고 BFS로 주변의 유효한 좌표들을 탐색한다. BFS에서 일반적으로 사용하는 큐가 아닌 우선순위 큐를 사용해서 좌표값과 가치를 함께 관리하도록 했다.

우선순위 큐로 인접한 좌표 중 검은 방을 최소한으로 지나치는 값을 가진 좌표부터 우선적으로 탐색할 수 있도록한다. 탐색한 좌표가 검은 방이라면 가치 값을 +1 해준다.

☁️ 코드

import sys, heapq

n = int(input())
graph = []
visited = [[False] * (n) for _ in range(n)]

for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().rstrip())))


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


def sol(x, y):
    q = []
    heapq.heappush(q, (0, x, y))

    while q:
        d, r, c = heapq.heappop(q)
        if r == n - 1 and c == n - 1:
            return d
        if visited[r][c]:
            continue
        visited[r][c] = True
        for a, b in zip(dx, dy):
            if -1 < r + a < n and -1 < c + b < n:
                if not visited[r + a][c + b]:
                    if graph[r + a][c + b] == 1:
                        heapq.heappush(q, (d, r + a, c + b))
                    else:
                        heapq.heappush(q, (d + 1, r + a, c + b))


print(sol(0, 0))