[백준 2665] 미로 만들기

이 문제는 2차원 배열때문에 BFS처럼 보일 수 있지만

문제의 목적이 최단경로를 찾는 것이 아니기 때문에 BFS로 풀면 안된다.

 

최소로 벽을 뚫으면서 목적지까지 가는 것이기 때문에

벽 뚫는 횟수를 기준으로 한 그리디적인 접근으로 풀어야한다.

 

그래서 다익스트라를 써야하고 목적지가 오른쪽 아래에 있다고 아래와 오른쪽 방향만 신경쓰면 안된다.

위로 가면서 벽을 덜 뚫는 루트가 있을 수 있기 때문

 

---

#include <iostream>
#include <bitset>
#include <queue>
#include <tuple>

#define SIZE 51
#define INF int(1e9)

using namespace std;

int N;
bitset<SIZE> map[SIZE];

// 최단경로가 아님. 벽을 최소로 뚫는 것이기 때문에 목적지가 오른쪽 끝에 있다고 왼쪽으로 움직이는 것을 배제하면 안됨!
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};

bool is_available(int y, int x)
{
    if (y < 1 || x < 1 || y > N || x > N)
    {
        return false;
    }
    return true;
}

int memo[SIZE][SIZE];

void solve()
{
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    pq.push({0, 1, 1});
    memo[1][1] = 0;

    int nexty, nextx;
    while (!pq.empty())
    {
        auto [cnt, y, x] = pq.top();
        pq.pop();

        for (int i = 0; i < 4; i++)
        {
            nexty = y + dy[i];
            nextx = x + dx[i];

            if (!is_available(nexty, nextx))
            {
                continue;
            }

            // 벽이라면
            if (map[nexty][nextx] == 0)
            {
                if (cnt + 1 < memo[nexty][nextx])
                {
                    memo[nexty][nextx] = cnt + 1;
                    pq.push({cnt + 1, nexty, nextx});
                }
            }
            // 벽이 아니면
            else
            {
                if (cnt < memo[nexty][nextx])
                {
                    memo[nexty][nextx] = cnt;
                    pq.push({cnt, nexty, nextx});
                }
            }
        }
    }
}

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

    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        for (int k = 1; k <= N; k++)
        {
            memo[i][k] = INF;
        }
    }

    char ch;
    for (int i = 1; i <= N; i++)
    {
        for (int k = 1; k <= N; k++)
        {
            cin >> ch;
            if (ch == '0')
            {
                map[i][k] = 0;
            }
            else
            {
                map[i][k] = 1;
            }
        }
    }

    solve();

    // for (int i = 1; i <= N; i++)
    // {
    //     for (int k = 1; k <= N; k++)
    //     {
    //         cout << memo[i][k] << " ";
    //     }
    //     cout << "\n";
    // }

    cout << memo[N][N];
    return 0;
}