[BFS] 백준 1697번 - 숨바꼭질 (정답률 25%)

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

1697번: 숨바꼭질

백준 BFS 연습문제이다.

계속해서 DFS와 BFS 연습문제들을 풀면서 좀더 느끼는 것은 어떨 때 BFS를, 어떨 때 DFS(혹은 백트래킹)를 활용해 문제를 해결해야겠다는 통찰이다.

 

*DFS로 문제를 풀기 좋은 문제들은 대략 이런 특징을 갖고있다.

1. 한 방향으로 계속 탐색해서 작은 탐색결과를 구하는 것이 전체 탐색결과를 구하는 것의 일부가 되는 문제

 

*BFS로 문제를 풀기 좋은 문제들은 대략 이런 특징이 있다.

1. 이 문제와 같이 가능한 모든 경우들에 대해 동시에 해답을 찾아가며 어느 한 가지라도 답을 찾는 경우를 발견하면 되는 문제

 

------

비유를 하자면 미로속에 갇혔다고 상상해보자.

 

(DFS 신봉자 A)

A는 갈 수 있는 길이 나오면 그 길로 계속 가보고, 막힌 길이 나오면 바로 이전 분기점으로 되돌아와 또 갈 수 있는 길로 계속 가는 성향이 있다. 이러면 미로에서 가볼 수 있는 모든 경로들을 하나 하나 순차적으로 완성해나가게 된다. 이는 DFS (백트래킹) 식 방법이다.

 

(BFS 신봉자 B)

B는 A와 다르게 몸을 여러개로 나누어 동시에 가볼 수 있는 외계인이라고 생각해보자. B는 분기점이 나오면 자신의 몸을 분리시켜 '동시에' 갈 수 있는 길로 모두 간다. 이러면 각 방향으로 가볼 수 있는 모든 경로들이 서서히 완성된다. 이는 BFS 식 방법이다.

 

** 또 다른 비유를 들자면

DFS가 어떤 지역에 처음 가보는 운전 미숙자로, 길이 있으면 그냥 가보고 그 길이 원하던 길이 아니면 다시 되돌아와 또 갈 수 있는 길이 있으면 가보는 것을 반복하는 사람으로 비유할 수 있고,

BFS는 물위에 떨어진 물감이 확산되는 현상과 유사하다고 할 수 있다. 큐의 앞에서부터 하나씩 동일 레벨의 요소들을 뽑아 가볼 수 있는 것을 큐에 push하므로 이렇게 생각해볼 수 있다.

------

 

어찌되었든간에, 이 문제는 1차원 경로상에서 목적지로 갈 수 있는 방법이 총 세 가지 (+1, -1, *2)가 있을 때, 최소 시간으로 동생의 위치로 가는데 걸리는 시간을 구하는 문제다. 쉽다. bfs에 처음에 걸린 시간 0을 넣어주고 수빈의 위치를 함께 pair로 큐에 넣어준 뒤, 경로의 범위와 방문 여부를 고려해 갈 수 있는 위치와 다음 시간을 큐에 계속 넣어주고 빼는 과정을 반복하다가, 동생의 위치에 도달하게 되면 더 이상 다음 시간에 이동할 필요가 없으므로 해당 시간을 정답으로 갱신해주면 된다.

 

아래는 BFS 소스코드. (4ms)

#include <iostream>
#include <queue>
#define maxlen 100000 + 1
using namespace std;
int N;
int sister;
int subin;
int Time=0;
bool check[maxlen];
void reset(){
    for (int i = 0; i < maxlen; i++)
        check[i] = false;
}
void bfs(int cur_time){
    queue<pair<int, int> > q;
    q.push(make_pair(subin, cur_time));
    check[subin] = true;
    while (!q.empty()){
        int front = q.front().first;
        int curT = q.front().second;
        if (front == sister){
            Time = curT;
            break;
        }
        q.pop();
        if (front - 1 >= 0)
            if (!check[front - 1]){
                q.push(make_pair(front - 1, curT + 1));
                check[front - 1] = true;
            }
        
        if (front + 1 < maxlen) 
            if (!check[front + 1]){
                q.push(make_pair(front + 1, curT + 1));
                check[front + 1] = true;
            }
        if (front * 2 < maxlen) 
            if (!check[front * 2]){
                q.push(make_pair(front * 2, curT + 1));
                check[front * 2] = true;
            }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    reset();
    cin >> subin >> sister;
    bfs(0);
    cout << Time << '\n';
    return 0;
}