[C++/BFS] 백준 1697 숨바꼭질

코드

1) pair 이용
현재 위치와 해당 위치까지 이동하는 데 걸린 시간을 함께 저장하기 위해 pair를 이용한다.

#include <iostream>
#include <queue>
using namespace std;
 
int bfs(int s, int e) {
    bool visit[100001] = { false }; // 왔던 곳에 중복해서 가는 경우를 피하기 위해
    queue<pair<int, int>> q; // 현재 위치, 걸린 시간
    q.push({ s,0 }); // 맨 처음의 위치, 시간을 큐에 넣음
 
    while (!q.empty()) {
        pair<int, int> now = q.front(); // 현재위치 걸린 시간
        visit[now.first] = true; // 방문 표시
        q.pop();
 
        if (now.first == e) // 도착한 경우 걸린 시간 리턴 후 종료
            return now.second;
        if (now.first-1 >= 0 && !visit[now.first - 1]) 
            q.push({ now.first - 1, now.second+1 }); // X서 X-1로 이동. 시간 1 증가
        if (now.first + 1 <= 100000 && !visit[now.first + 1]) 
            q.push({ now.first + 1, now.second+1 }); // X서 X+1로 이동. 시간 1 증가
        if (now.first * 2 <= 100000 && !visit[now.first * 2])
            q.push({ now.first * 2, now.second+1 }); // X서 X * 2로 이동. 시간 1 증가
    }
}
 
int main() {
    int start, end;
    cin >> start >> end;
    cout << bfs(start, end) << endl;
}
 

2) pair 없이 bfs
while문 내에 for문을 둬 같은 시간일 때의 위치이동은 한번에 처리

#include <iostream>
#include <queue>
using namespace std;
 
int bfs(int s, int e) {
    bool visit[100001] = { false }; // 왔던 곳에 중복해서 가는 경우를 피하기 위해
    queue<int> q; // 이동했던 위치를 담는 큐
    q.push(s); // 맨 처음의 위치를 큐에 넣음
    int time = 0; // 맨 처음 시간
 
    while (!q.empty()) {
        int size = q.size();
        while(size--){
            int now = q.front(); // 현재위치
            visit[now] = true; // 방문 표시
            q.pop();
 
            if (now == e) 
                return time; // 도착한 경우 걸린 시간 리턴 후 종료
            if (now-1 >= 0 && !visit[now - 1]) 
                q.push(now - 1); // X서 X-1로 이동.
            if (now + 1 <= 100000 && !visit[now + 1]) 
                q.push(now + 1); // X서 X+1로 이동. 시간 1 증가
            if (now * 2 <= 100000 && !visit[now * 2])
                q.push(now * 2); // X서 X * 2로 이동. 시간 1 증가
        }
        time++; // 시간 증가
    }
}
 
int main() {
    int start, end;
    cin >> start >> end;
    cout << bfs(start, end) << endl;
}
​