[크래프톤 정글] 백준 2665번 미로만들기

다익스트라 알고리즘을 공부 하면서 풀어볼수 있는 문제를 찾다가 미로만들기 문제를 풀어보았는데 다익스트라가 어떤 알고리즘 인지 보여주는데 적합한 문제인것 같아 정리 해보았다.

문제 개요

"미로 만들기" 문제(백준 문제 번호: 2665)는 흑백 미로에서 최소한의 방을 바꾸어 시작점에서 도착점까지 도달하는 최단 경로를 찾는 문제이다.

문제 설명

• 미로는 NxN 크기의 정사각형으로, 각 칸은 흰 방(0) 또는 검은 방(1)으로 이루어져 있다.
• 흰 방(0)은 그대로 지나갈 수 있지만, 검은 방(1)은 흰 방으로 바꾸어야만 지나갈 수 있다.
• 목표는 시작점 (0, 0)에서 도착점 (N-1, N-1)까지 도달하는데 필요한 최소한의 검은 방 변환 횟수를 구하는 것이다.

다익스트라 알고리즘을 사용한 접근

그래프 모델링

• 각 방을 그래프의 노드로 간주한다.
• 인접한 방들 사이의 경로는 엣지로 표현된다.
• 방이 검은색(1)일 경우, 그 경로의 가중치는 1로 설정하고, 방이 흰색(0)일 경우 가중치는 0으로 설정한다.

알고리즘 단계

1. 초기화:

   • 출발점(0, 0)에서 다른 모든 방까지의 거리를 무한대로 설정한다.
   • 출발점의 거리는 0으로 설정하고, 우선순위 큐에 (0, 0, 0)을 삽입한다. 여기서 (거리, x, y) 형식이다.

2. 반복:

   • 큐에서 가장 작은 거리를 가진 노드를 꺼내 현재 노드로 설정한다.
   • 현재 노드에서 인접한 모든 노드를 탐색한다.
   • 인접한 방으로 이동하는 경로의 가중치를 계산하고, 그 경로가 더 짧다면 거리를 갱신하고 큐에 삽입한다.

3. 종료 조건:

   • 목표 지점 (N-1, N-1)에 도달했을 때의 최소 거리가 답이 된다.

다익스트라 알고리즘 코드 (Python)

import heapq

def dijkstra_maze(n, maze):
    # 거리 저장소 초기화: 무한대로 설정
    distances = [[float('inf')] * n for _ in range(n)]
    distances[0][0] = 0  # 시작점의 거리

    # 우선순위 큐 초기화
    priority_queue = [(0, 0, 0)]  # (거리, x, y)

    # 방향 벡터 (상하좌우)
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while priority_queue:
        current_distance, x, y = heapq.heappop(priority_queue)

        # 목표 지점에 도달하면 종료
        if x == n - 1 and y == n - 1:
            return current_distance

        # 인접한 모든 노드 탐색
        for dx, dy in directions:
            nx, ny = x + dx, y + dy

            if 0 <= nx < n and 0 <= ny < n:
                # 현재 방의 상태에 따른 가중치 설정
                next_distance = current_distance + (1 if maze[nx][ny] == 1 else 0)

                # 더 짧은 경로를 찾으면 갱신
                if next_distance < distances[nx][ny]:
                    distances[nx][ny] = next_distance
                    heapq.heappush(priority_queue, (next_distance, nx, ny))

    return distances[n-1][n-1]

# 예시 입력
n = 8
maze = [
    [0, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 1, 1, 0],
    [1, 1, 0, 1, 0, 0, 0, 0],
    [1, 1, 0, 0, 1, 1, 1, 1],
    [1, 1, 1, 0, 0, 0, 0, 0],
    [1, 1, 1, 1, 1, 1, 1, 0],
    [1, 0, 0, 0, 0, 0, 1, 0],
    [1, 1, 1, 1, 1, 1, 1, 0]
]

# 최소 검은 방 변환 횟수 출력
print(dijkstra_maze(n, maze))  # 출력: 2

코드 동작 원리

1. 초기화 단계

   distances = [[float('inf')] * n for _ in range(n)]
   distances[0][0] = 0
   priority_queue = [(0, 0, 0)]

   • distances 배열을 생성하여 시작점에서 각 방까지 도달하는 최소 거리를 저장한다. 처음에는 모든 방까지의 거리를 무한대(inf)로 설정한다.
   • 시작점 (0, 0)의 거리를 0으로 설정하고, 이를 큐에 추가한다. 이 큐는 현재까지 방문한 방 중 가장 적은 비용(즉, 최소한으로 검은 방을 바꾼 횟수)을 기준으로 탐색할 다음 방을 선택하기 위해 사용된다.
   • priority_queue는 우선순위 큐로, 가장 비용이 적은 경로를 먼저 탐색한다.

2. 큐에서 방 꺼내기 및 탐색

   while priority_queue:
       current_distance, x, y = heapq.heappop(priority_queue)

   • 큐에서 가장 작은 current_distance 값을 가진 방을 꺼낸다. 이 current_distance는 (x, y) 위치까지 도달하기 위해 변환한 검은 방의 수를 의미한다.
   • (x, y)는 현재 위치한 방의 좌표이다.

3. 목표 지점에 도달했는지 확인

   if x == n - 1 and y == n - 1:
       return current_distance

   • 현재 방이 목표 지점 (N-1, N-1)인지 확인한다. 만약 도착했다면, 이때의 current_distance가 최소한으로 검은 방을 변환한 횟수이므로 결과로 반환한다.

4. 인접 방 탐색

   for dx, dy in directions:
       nx, ny = x + dx, y + dy
       if 0 <= nx < n and 0 <= ny < n:
           next_distance = current_distance + (1 if maze[nx][ny] == 1 else 0)

   • 현재 위치에서 상하좌우 인접한 방으로 이동할 수 있는지 확인한다. directions 리스트를 사용해 (x, y)에서 갈 수 있는 네 방향을 각각 계산한다.
   • (nx, ny)는 이동할 수 있는 인접 방의 좌표이다. 이 방이 미로 범위 안에 있는지 (0 <= nx < n 및 0 <= ny < n) 확인한다.
   • 그 방이 흰 방(0)이라면 가중치가 0이므로 next_distance는 current_distance와 동일하다.
   • 그 방이 검은 방(1)이라면 가중치가 1이 추가되므로, next_distance는 current_distance + 1이 된다. 즉, 검은 방을 하나 더 바꾸어야 한다는 의미다.

5. 거리 갱신 및 큐에 추가

   if next_distance < distances[nx][ny]:
       distances[nx][ny] = next_distance
       heapq.heappush(priority_queue, (next_distance, nx, ny))

   • next_distance가 현재 알고 있는 (nx, ny)까지의 최소 거리보다 작다면, 이 새로운 경로가 더 효율적이라는 의미다. 따라서 distances 배열을 갱신한다.
   • 갱신한 후, 이 새로운 경로를 큐에 추가한다. 이렇게 하면 다음 번에 큐에서 꺼낼 때 이 방을 더 빨리 탐색할 수 있다.

6. 반복 탐색

   • 이 과정이 목표 지점에 도달할 때까지 계속된다. 매번 큐에서 가장 작은 current_distance를 가진 방을 꺼내어, 그 방의 인접한 방들을 탐색하고 거리를 갱신한다.
   • 모든 탐색이 끝나면, 가장 효율적으로 검은 방을 바꾸어 도착점에 도달하는 방법을 찾게 된다.

요약

• 우선순위 큐를 사용해 가장 적은 비용(즉, 가장 적게 검은 방을 바꾼 경우)의 경로를 먼저 탐색한다.
• 각 방의 최소 거리를 저장하면서, 더 짧은 경로가 발견될 때마다 갱신한다.
• 최종적으로 목표 지점에 도달했을 때의 최소 거리가 최적의 경로이며, 이는 검은 방을 최소한으로 바꾼 횟수를 나타낸다.