백준 1697 숨바꼭질

앞에 문제들과 다르게 그래프처럼 생긴 문제들을 bfs로 푸는 것이 아니라, 그래프처럼 보이지 않는 문제를 그래프로 바꾸어 bfs로 푼다.

 

한 번 이동하는데 1초가 걸리므로 가중치를 1로 생각할 수 있다.

최대 위치가 10만이므로 bfs로 풀 수 있다.

 

처음에는 dist 배열만 선언해서 방문할 때마다 1을 더해주었다.

어짜피 한 번 방문하고 나서 이후에 방문하면 그 값이 더 커지므로 최소 비용을 만족할 수 없다고 생각했기 때문이다.

계속 틀렸다고 나와서 생각해보니, 첫 시작점도 dist는 0이기 때문에 계속 반복해서 방문하게 되는 문제가 발생한다.

이를 수정했더니 맞게 나왔다.

 

자세한 설명은 주석으로..

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
 
//bool visit[100001];
int dist[100001];
 
int main(int argc, char** argv) {
    int n, k;
    cin >> n >> k;
 
    queue<int> q;
    q.push(n);
    //visit[n] = true;
    
    while (!q.empty()) {
        int position = q.front();
        q.pop();
 
        int prev = position - 1;
        int next = position + 1;
        int jump = position * 2;
 
        if (prev >= 0) {
            //if(!visit[prev]) 원래라면 이렇게 visit를 통해 한다.
            //prev != 0은 시작점 n이 0이기 때문에 이를 계속 방문하는 것을 막는다.
            if (dist[prev] == 0 && prev != n) {
                q.push(prev);
                dist[prev] = dist[position] + 1;
                //visit[prev] = true;
            }
        }
        if (next <= 100000) {
            if (dist[next] == 0 && next != n){
                q.push(next);
                dist[next] = dist[position] + 1;
                //visit[next] = true;
            }
        }
        if (jump <= 100000) {
            if (dist[jump] == 0 && jump != n) {
                q.push(jump);
                dist[jump] = dist[position] + 1;
                //visit[jump] = true;
            }
        }
    }
 
    printf("%d\n", dist[k]);
 
    return 0;
}