[ 백준 2665 ] 미로 만들기 (C++)

백준의 미로 만들기 (2665) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 검은 방을 흰방으로 최소한의 갯수로 바꿨을 때, 도착점까지 가는데 바꾼 문의 최소 갯수를 찾아야 하는 문제이다.

   본인은 너비우선탐색(BFS)을 이용해서 접근해 보았는데, 방문 체크를 할 때, 단순히 이미 방문한 좌표라면

   방문을 안하게 한 것이 아닌, 바꾼 문의 갯수를 통해서 체크를 해주었다.

   int Visit[][] 라는 2차원 int형 배열을 만들어주었는데, Visit[a][b] = c 의 의미는 "지금까지 탐색한 바로는, (a, b)까지

   오는데 검은 방을 흰방으로 바꾼 갯수는 c개입니다." 를 의미한다.

   즉, 이미 방문한 좌표더라도, 검은 방을 흰 방으로 바꾼 갯수가 더 적은 경로라면 다시 재방문을 한다는 것이다.

   최종적으로, 우리는 Visit[N][N]의 값을 출력하게 되면, (0, 0)에서부터 (N ,N)까지 오는데 검은방을 흰 방으로 바꾼

   최소 갯수개가 저장되어 있을 것이다.

   또한, 최단 경로를 찾는 문제가 아니다. 단순히, 제일 빨리 도착하는 경우가 아닌, 바꾼 횟수를 최소화 해야 하는

   문제이기 때문에, (N ,N)에 도착한다고 하더라도 BFS탐색을 종료시키는것이 아니라, Queue가 모두 빌 때 까지

   탐색을 해줘야 한다 !

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<string>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int N;
int MAP[MAX][MAX];
int Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        string S; cin >> S;
        for (int j = 0; j < S.length(); j++)
        {
            MAP[i][j] = S[j] - '0';
        }
    }
}
 
void Solution()
{
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            Visit[i][j] = 987654321;
        }
    }
 
    queue<pair<int, int>> Q;
    Q.push(make_pair(0, 0));
    Visit[0][0] = 0;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                if (MAP[nx][ny] == 1)
                {
                    if (Visit[nx][ny] > Visit[x][y])
                    {
                        Visit[nx][ny] = Visit[x][y];
                        Q.push(make_pair(nx, ny));
                    }
                }
                else
                {
                    if (Visit[nx][ny] > Visit[x][y] + 1)
                    {
                        Visit[nx][ny] = Visit[x][y] + 1;
                        Q.push(make_pair(nx, ny));
                    }
                }
            }
        }
    }
}
 
void Solve()
{
    Input();
    Solution();
    cout << Visit[N - 1][N - 1] << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}