백준 숨바꼭질 [c++]

숨바꼭질 실버1

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

문제 풀이

• 일차원배열이지만 그래프탐색 문제이다.
• bfs를 이용하는것이 적절해보임.
• 탑색까지 걸린 level을 count하기 위해 위치정보와 cnt를 pair로 큐에 삽입한다.
• 실수 1. visited를 만들어놓고 방문할때마다 표시해주지 않는 실수함.
• 실수 2. 수빈이와 동생의 위치가 동일한 경우 0이 아닌 1로 표기된다. (0으로 표기되어야 함.) 내가 작성한 코드의 경우 다음위치가 동생위치인지 비교하기 때문에 예외처리가 필요했다.

코드

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

int n, k;
int area[100001];
int visited[100001];
queue<pair<int, int> > q;
int cnt = 0;

void init()
{
    for(int i = 0; i <= 100000; i++)
    {
        area[i] = 0;
        visited[i] = 0;
    }
}

void bfs(int s){
    visited[s] = 1;
    q.push(make_pair(s, cnt));

    while(!q.empty()){
        int ns = q.front().first;
        cnt = q.front().second;
        q.pop();
        visited[ns] = 1;
        int ns_f = ns + 1;
        int ns_b = ns - 1;
        int ns_t = 2 * ns;
        if(ns_f == k || ns_b == k || ns_t == k){
            cout << cnt + 1 << endl;
            return;
        }

        if(ns_f >= 0 && ns_f <= 100000 && visited[ns_f] == 0){
            q.push(make_pair(ns_f, cnt + 1));
        }
        if(ns_b >= 0 && ns_b <= 100000 && visited[ns_b] == 0){
            q.push(make_pair(ns_b, cnt + 1));
        }
        if(ns_t >= 0 && ns_t <= 100000 && visited[ns_t] == 0){
            q.push(make_pair(ns_t, cnt + 1));
        }
    }
}

int main()
{
    cin >> n >> k;
    init();
    if(n != k){
        bfs(n); 
    } else{
        cout << 0 << endl;
    }
    return 0;
}

총평

• bfs에서 정답이 트리의 어떤 레벨인지 확인하기 위해 위치와 level을 pair로 다루는 방법을 알 수 있었음.
• 예외처리 항상 주의!

• ps
• bfs