[백준] 2665 - 미로만들기 (Python)

문제 링크

알고리즘

• 다익스트라

Tip

• 하얀 방으로 이동할 때를 가중치 0으로, 검은 방으로 이동할 때를 가중치 1로 설정하고 목표 지점까지의 최단 거리를 구하면 해결할 수 있는 문제
• 우선순위 큐를 사용해서 가중치가 0인 간선(경로)를 우선적으로 택한다. ( 다익스트라 알고리즘 )
• 파이썬의 내장 자료구조인 heapq를 사용한다.

가중치가 0이나 1일 경우 큐를 두 개 생성해서 BFS로 해결하는 방법도 있지만 우선순위 큐를 사용한 다익스트라 알고리즘을 사용했다.

풀이

최소 힙(우선순위 큐)에는 cost(거리), r(행 인덱스), c(열 인덱스) 정보가 들어있다.

-> 출발지로부터 r행 c열까지의 거리

큐에 있는 것들 중 cost(거리)가 가장 작은 요소를 꺼낸다. 이 때 꺼낸 요소 -> 출발지로부터 r행 c열까지의 최단거리

꺼낸 요소에서 상하좌우 4방향에 대해 각각 인덱스 초과, 방문 여부를 조사하고 가능하다면 우선순위 큐에 넣는다.

이 때 큐에 새로 넣는 cost는 현재 cost + (0 or 1) 으로 설정한다. (흰 방 or 검은 방)

만약 큐에서 꺼낸 행과 열이 도착지와 같다면 출력 후 프로그램을 종료한다.

코드

import sys
import heapq

input = sys.stdin.readline
N = int(input())

# 미로 생성
maze = [list(map(int, list(input().rstrip()))) for _ in range(N)]

# 미로를 탐색할 큐를 생성
queue = [[0, 0, 0]]

# 방문처리할 리스트 NxN
visited = [[False for _ in range(N)] for _ in range(N)]

# 상하좌우 4방향
direction = [(1, 0), (0, -1), (-1, 0), (0, 1)]

while queue:
    cost, r, c = heapq.heappop(queue)

    # 도착지면 출력 후 프로그램 종료
    if r == N - 1 and c == N - 1:
        print(cost)
        exit(0)

    # 상하좌우 4방향 탐색 (인덱스 초과, 방문 했는지 검사)
    for d in direction:
        next_r = r + d[0]
        next_c = c + d[1]
        if 0 <= next_r < N and 0 <= next_c < N and not visited[next_r][next_c]:
            # 흰 방, 검은 방 종류에 따라 가중치 0 or 1로 설정
            next_cost = 0 if maze[next_r][next_c] == 1 else 1
            visited[next_r][next_c] = True
            heapq.heappush(queue, [cost + next_cost, next_r, next_c])