[C++]백준(BOJ) - 30689 미로만들기(다익스트라)

 

난이도 : 골IV

풀이 시간 : 20분

알고리즘 유형 : BFS, 다익스트라

풀이 방법 : 우선순위를 이용해 범위 기반 탐색(상하좌우)

 

 

문제 링크

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

 

 

문제 예시

n×n 바둑판 모양이고, 일부분은 검은 방이고 나머지는 모두 흰 방이다.
검은 방은 들어갈 수 없고, 붙어 있는 두 개의 흰 방 사이에는 
문이 있어서 지나다닐 수 있다.

검은 방 몇 개를 흰 방으로 바꿀 수 있다.  

-> n x n 격자 이며, 검은방은 흰색으로 바꿀 수 있다.(cost 증가)

윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고,
아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다.
-> 예외처리 할 필요 없음

시작방에서 출발 -> 끝방으로 도착하는 것이 목적인데,
부득이 검은 방 몇 개를 흰 방으로 바꾸어야 한다.
n×n 바둑판 모양, 일부분은 검은 방이고 나머지는 모두 흰 방이다.
검은 방은 들어갈 수 없다.
아래 그림은 n=8인 경우의 한 예이다.

위 그림에서는 두 개의 검은 방(예를 들어 (4,4)의 방과 (7,8)의 방)을 흰 방으로 바꾸면,
시작방에서 끝방으로 갈 수 있지만, 어느 검은 방 하나만을 흰 방으로 바꾸어서는 불가능하다.

검은 방에서 흰 방으로 바꾸어야 할 최소의 수를 구하는 프로그램을 작성하시오.
단, 검은 방을 하나도 흰방으로 바꾸지 않아도 되는 경우는 0이 답이다.

 

 

문제 풀이 방식

• 최소 비용 경로 탐색: 우선순위 큐(priority_queue)를 사용하여 현재까지
  변경된 검은 방의 수(cost)가최소인 경로를 탐색합니다.
  changeStack[x][y]는 (x, y) 좌표에 도달하기 위해 필요한 최소 변경 횟수를 저장합니다.
  
  
• BFS와 다익스트라 결합: 흰 방(1)을 만나면 cost를 유지하고,
  검은 방(0)을 만나면 cost를 1 증가시킵니다. 이 과정에서 우선순위 큐를 통해
  비용이 작은 경로부터 탐색하여 최소 변경 횟수를 구합니다.

 

 

 

아래는 코드입니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

int n;
string board[51];
int changeStack[51][51];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for (int i = 0; i < n; ++i)
    {
        fill(changeStack[i], changeStack[i] + n, 1e9);
        cin >> board[i];
    }


    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;

    changeStack[0][0] = 0;
    pq.push({0, 0, 0});


    while(!pq.empty())
    {
        auto[cost, x, y] = pq.top();
        pq.pop();

        if (changeStack[n - 1][n - 1] != 1e9)
        {
            cout << changeStack[x][y];
            break;
        }
    

        if(cost != changeStack[x][y])
            continue;

        for (int dir = 0; dir < 4; ++dir)
        {
            int nx = dx[dir] + x;
            int ny = dy[dir] + y;
        
            if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;

            if (board[nx][ny] == '1' && changeStack[nx][ny] > cost)
            {
                changeStack[nx][ny] = cost;
                pq.push({cost, nx, ny});
            }
            else if (board[nx][ny] == '0' && changeStack[nx][ny] > cost + 1)
            {
                changeStack[nx][ny] = cost + 1;
                pq.push({ cost + 1, nx, ny });
            }
        }
    }

    return 0;
}