[Algorithm] 백준 17836 공주님을 구해라! - C++ ,BFS

17836번: 공주님을 구해라!

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

int n, m, timeLimit;
int map[101][101];
bool visit[101][101][3];
int moveX[] = { 0, 0, 1, -1 };
int moveY[] = { 1, -1, 0, 0 };

int IsOut(int y, int x){
    if(y < 1 || x < 1 || y > n || x > m)
        return true;
    return false;
}

void FindPrincess(){
    queue<pair<pair<int, int>, pair<bool, int>>> q;
    q.push({{1, 1}, {false, 0}});
    visit[1][1][0] = true;

    while (!q.empty()){
        int curY = q.front().first.first;
        int curX = q.front().first.second;
        bool haveGram = q.front().second.first;
        int curTime = q.front().second.second;
        q.pop();

        // complete
        if(curTime > timeLimit){
            break;
        }
        if(curX == m && curY == n){
            cout << curTime << '\n';
            return;
        }

        // search next position
        for(int i = 0; i < 4; i++){
            int nextY = curY + moveY[i];
            int nextX = curX + moveX[i];

            if(IsOut(nextY, nextX)) continue;
            // have gram
            if(haveGram && !visit[nextY][nextX][1]){
                visit[nextY][nextX][1] = true;
                q.push({{nextY, nextX}, {haveGram, curTime+1}});
                continue;
            }

            if(visit[nextY][nextX][0])  continue;
            if(map[nextY][nextX] == 0){
                visit[nextY][nextX][0] = true;
                q.push({{nextY, nextX}, {haveGram, curTime+1}});
                
            }else if(map[nextY][nextX] == 2){
                visit[nextY][nextX][1] = true;
                q.push({{nextY, nextX}, {true, curTime+1}});
            }
        }
    }
    

    cout << "Fail\n";
}

int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(visit, false, sizeof(visit));

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

    FindPrincess();
    return 0;
}

---

 간단해 보이는 문제였는데 이상하게 메모리 초과라던지 double free 오류가 나와서 오래 걸린 문제입니다. double free는 왜 아직도 문제인지를 잘 모르겠습니다.

 

 일단 평범한 BFS와는 다르게 그람을 먹었을때랑 먹지 않았을때의 visit 체크를 따로 해줘야 합니다. 이걸 하지 않으면 메모리 초과가 나오더라구요. 그 외에는 평범함 BFS로 풀이하시면 됩니다.