[백준 13549] - 숨바꼭질 3(BFS) C++

문제

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

13549번: 숨바꼭질 3

접근방법

BFS를 활용해 최단거리를 구하는 문제다.

 

queue<pair<int, int>>를 정의하고, pair.first에 위치 저장하고, pair.second에 이동시간 저장했다.

 

포인트는 방문여부 체크로 중복을 줄여주는 데 있었다.

방문여부 체크를 안하면 메모리 초과로 실패했다.

 

1 2가 입력되면, 0이 정답이 되어야 하는데, 1이 나왔다.

알고보니 함수 리턴하는 과정에서 순서가 꼬여있었다.

 

1에서 +1을 해도 2고, 1 * 2를 해도 2다.

순간이동 하는 경우, 0초만에 이동할 수 있기때문에,

순간이동을 먼저 검사해줘야 더 짧은 거리를 구할 수 있다.

따라서 여기서는 pos * 2를 먼저 검사해야 더 짧은 거리를 구할 수 있다.

코드

int n, k;
queue<pair<int, int>> mq;
int answer;
vector<bool> Visit(100001, false);
void sumbakkocgil(int from) {
    mq.push({from, 0});
    while(!mq.empty()) {
        auto [pos, time] = mq.front();
        mq.pop();
        Visit[pos] = true;
        if (pos == k) {
            answer = time;
            return;
        } else if (pos * 2 == k) {
            answer = time;
            return;
        } else if (pos + 1 == k || pos - 1 == k) {
            answer = time + 1;
            return;
        } 
        if (pos * 2 < 100001 && !Visit[pos * 2]) mq.push({pos * 2, time});
        if (pos - 1 >= 0 && !Visit[pos - 1]) mq.push({pos - 1, time + 1});
        if (pos + 1 < 100001 && !Visit[pos + 1]) mq.push({pos + 1, time + 1});
   }
}

개선할 점

최대한 중복을 제거해보려고 노력하자.