[Baekjoon 2665 / python / 골드4] 미로 만들기

import heapq

import sys

INF = int(1e9)

input = sys.stdin.readline

N = int(input())

board = []

for _ in range(N):  # 미로 입력받기

    board.append(list(map(int, input().strip())))

distroy = [[INF for _ in range(N)] for _ in range(N)]  # 부순갯수

visited = [[False for _ in range(N)] for _ in range(N)]  # 방문목록

def goingNogoing(x, y):  # 갈지말지 정하는함수

    if 0 <= x < N and 0 <= y < N and visited[x][y] == False:

        return True

    return False

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

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

def dijkstra():

    queue = []

    heapq.heappush(queue, (0, 0, 0))  # 부순갯수, x, y

    visited[0][0] = True

    distroy[0][0] = 0

    while queue:

        for _ in range(len(queue)):

            dist, cx, cy = heapq.heappop(queue)  # 큐에서 현재까지 부순갯수, x, y 빼기

            if cx == N - 1 and cy == N - 1:  # 도착했다면 부순갯수 리턴

                return dist

           

            for i in range(4):  # 상하좌우 반복

                nx = cx + dx[i]

                ny = cy + dy[i]

                if goingNogoing(nx, ny):

                    if board[nx][ny] == 0:  # 다음방이 검은방이면

                        cost = dist + 1  

                        distroy[nx][ny] = cost  # 부순갯수 +1 해서 테이블 갱신

                        heapq.heappush(queue, (cost, nx, ny))  # 갱신했으니 큐에 넣기

                        visited[nx][ny] = True  # 방문체크

                    else:

                        distroy[nx][ny] = dist  # 부순갯수 그대로 테이블 갱신

                        heapq.heappush(queue, (dist, nx, ny))  # 갱신했으니 큐에 넣기

                        visited[nx][ny] = True  # 방문체크

print(dijkstra())

 

BFS와 다익스트라 알고리즘을 혼합해 사용하는 문제이다. 사실 최근에 DFS BFS 다익스트라 위상정렬 등 여러가지 알고리즘을 너무 단기간에 대량을 흡수하고 있어서 뭐가 뭔지 헷갈릴 지경이다.

 

BFS처럼 진행하지만 heapq를 사용해서 벽 부순갯수를 첫번째 원소로 저장한다(흰색 방으로 바꾼 걸 부쉈다고 표현하겠다). 그러면 heapq는 최소힙으로 동작하기 때문에 자연스럽게 벽을 가장 적게 부순 경우의 수를 꺼내게 된다.

그렇게 상/하/좌/우를 검사해서 방문체크를 해가며 계속 distroy 테이블을 갱신하면, 목적지에 도착했을 때의 부순 갯수가 바로 정답이 된다. 다시 말하지만 최소 힙으로 동작하기 때문에 바로 정답이 도출된다.

 

BFS와 다익스트라를 혼용해서 사용해야 해서 꽤 헷갈리는 문제였다.