[C/C++] 백준 #2665 미로만들기(다익스트라)

이번 문제는 얼듯 보면 미로를 백트래킹(또는 깊이우선탐색) 등으로 풀어나갈 것 같지만, 벽을 가는 곳을 간선 웨이트를 1로, 벽이 없는 곳을 간선 웨이트 0으로 생각하고 다익스트라 알고리즘을 적용하면 풀기 편합니다.

 

maze

 

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

 

제가 작성한 소스의 설명입니다.  일반적인 다익스트라 알고리즘을 이용했는데, 우선순위큐에 저장될 값들을 비트연산을 통해서 정수형(int)로 만들어서 했습니다.

 

1. **입력 받기**: 사용자로부터 미로의 크기 \( n \)과 미로의 지도를 입력받습니다.
2. **우선순위 큐 사용**: 미로의 각 방을 탐색하기 위해 우선순위 큐를 사용합니다. 이 큐는 현재 경로에서 흰 방으로 바꿔야 할 검은 방의 수를 우선순위로 사용합니다.
3. **탐색 초기화**: 탐색을 시작하기 위해 시작 위치(0, 0)를 큐에 넣고, 이미 방문한 방을 표시하기 위해 해당 위치를 'v'로 마크합니다.
4. **탐색 수행**: 큐가 비어있지 않을 때까지 다음 과정을 반복합니다:
   - 큐에서 현재 위치와 지금까지 바꾼 검은 방의 수를 꺼냅니다.
   - 현재 위치가 목표 위치(n-1, n-1)인지 확인하고, 도달했다면 지금까지 바꾼 검은 방의 수를 출력하고 종료합니다.
   - 현재 위치에서 이동할 수 있는 4방향(상하좌우)을 검사하여 유효한 위치로 이동합니다. 만약 이동할 위치가 검은 방이라면, 큐에 추가할 때 흰 방으로 바꿔야 하므로 카운트를 증가시킵니다. 이동할 위치를 'v'로 마크하여 중복 방문을 방지합니다.
5. **종료**: 목표 위치에 도달했을 때 결과를 출력하고 프로그램을 종료합니다.

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2665
//        - by Aubrey Choi
//        - created at 2019-07-12
//------------------------------------------------
#include <stdio.h>
#include <queue>

int main()
{
    int n;
    char map[50][51];
    std::priority_queue<int> queue;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%s", map[i]);
    queue.push(1000<<16);
    map[0][0] = 'v';
    while(!queue.empty())
    {
        int t = queue.top();
        queue.pop();
        int p = 1000-(t >> 16), r = (t >> 8) & 255, c = t & 255;
        if(r == n - 1 && c == n - 1)
        {
            printf("%d\n", p);
            break;
        }
        const int d[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
        for(int i = 0; i < 4; i++)
        {
            int nr = r + d[i][0], nc = c + d[i][1];
            if(nr < 0 || nr >= n || nc < 0 || nc >= n || map[nr][nc] == 'v') continue;
            if(map[nr][nc] == '0') queue.push(((999 - p) << 16) | (nr << 8) | nc);
            else queue.push(((1000 - p) << 16) | (nr << 8) | (nc));
            map[nr][nc] = 'v';
        }
    }
    return 0;
}