[Algorithm] 백준 2665 미로 만들기 - C++ ,BFS

2665번: 미로만들기

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int n;
const int MAX = 2600;
char map[51][51];
int wallBreak[51][51];
int moveX[] = { 0, 0, 1, -1 };
int moveY[] = { 1, -1, 0, 0 };

bool IsOut(int y, int x){
    if(x < 0 || y < 0 || x >= n || y >= n) 
        return true;
    return false;
}

// void MakeMaze(){
//     queue<pair<int, int>> q;
//     q.push({0, 0});
//     wallBreak[0][0] = 0;

//     while(!q.empty()){
//         int curY = q.front().first;
//         int curX = q.front().second;
//         q.pop();
//         for(int i = 0; i < 4; i++){
//             int nextY = curY + moveY[i];
//             int nextX = curX + moveX[i];
//             if(IsOut(nextY, nextX)) continue;

//             int nextIsWall = (map[nextY][nextX] == '0') ? 1 : 0;

//             if(wallBreak[curY][curX] + nextIsWall < wallBreak[nextY][nextX]){
//                 wallBreak[nextY][nextX] = wallBreak[curY][curX] + nextIsWall;
//                 q.push({nextY, nextX});
//             }
//         }
//     }
// }
void MakeMaze(){
    queue<pair<int, pair<int, int>>> q;
    q.push({0, {0, 0}});
    wallBreak[0][0] = 0;

    while(!q.empty()){
        int count = q.front().first;
        int curY = q.front().second.first;
        int curX = q.front().second.second;
        q.pop();
        
        if(count > wallBreak[curY][curX])   continue;

        for(int i = 0; i < 4; i++){
            int nextY = curY + moveY[i];
            int nextX = curX + moveX[i];
            if(IsOut(nextY, nextX)) continue;

            int nextIsWall = (map[nextY][nextX] == '0') ? 1 : 0;

            if(count + nextIsWall < wallBreak[nextY][nextX]){
                q.push({count + nextIsWall, {nextY, nextX}});
                wallBreak[nextY][nextX] = count + nextIsWall;
            }
        }
    }
}
int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // input
    cin >> n;
    for(int i = 0; i <n; i++){
        for(int j = 0; j < n; j++){
            cin >> map[i][j];
        }
    }

    // search
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            wallBreak[i][j] = MAX;
    MakeMaze();

    // print
    cout << wallBreak[n-1][n-1] << '\n';
}

---

 단순히 BFS를 하면서 돌아주면 되는 문제로 벽의 정보를 저장할 배열 map과 각 지점까지 도달하기 위해서 벽을 부순 최소 횟수를 저장하는 wallBreak 배열 2개를 사용했습니다. 

 

 추가적으로 함수를 2개 작성해 봤는데 둘 다 성능은 같습니다. 편한 방법을 체택하면 될 것 같네요. 함수를 2개 준비하게 된 사연은 if(Isout()) 에서 continue;를 넣지 않고 해서 그런거 같습니다. 덕분에 런타임 에러도 보고 오류도 좀 있었네요.