Boj 1697 c++ 숨바꼭질 (백준 복귀)

정말 오랜만에 돌아온 PS. 이제 시험이 끝났으니 다시 열심히 해보겠다. 기억을 되살리는게 조금 힘들 수도....

 

문제는 다음과 같다.

 

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

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

 

태그는 격자그래프, 너비우선 탐색이었는데 막상 격자그래프로 풀었는지는 모르겠다. 우선 현재위치 N과 동생의 위치 K가 주어지므로 격자그래프의 기본 탐색 방식인 4방향 탐색에서 착안하여 dx[3]={-1, 1, (현재 위치 두배)} 형태로 구현하였다.

 

이렇게 위치를 변경시키며 마침내 동생의 위치에 도달하면 BFS를 종료한다. 이때, 구해야 하는 것은 최소 이동횟수이므로 이전에 풀었던 문제들과 유사하게 dist 배열을 이용해 누적해준다. 코드의 아이디어를 생각하는데에는 오래걸리지 않았지만 몇가지 오류들이 발생해 여러번 제출하여 맞췄다. 특히 전역변수가 덮어씌워지는 문제와 불필요한 배열, 또는 큐의 공간 사용, 논리오류로 인한 불필요한 값의 누적, 등 미묘한 문제들을 알아차리는 것이 핵심이었다.

제출한 코드는 다음과 같다.

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

vector<int> dist(100001);
vector<int> visited(100001);
queue<int> q;

void BFS(int start, int goal){
    int nx;
    int dx[2]={-1, 1,};
    q.push(start);
    visited[start]=1;//방문처리

    while(!q.empty()){
        int start=q.front();//시작값 초기화
        for(int i=0; i<3; i++){
            (i!=2)? nx=dx[i]+start : nx=start*2;
            if(nx<0 || nx>100000)
                continue;//인덱스초과 방지
            if(!visited[nx]){//미방문 시
                q.push(nx);//탐색 예약
                visited[nx]=1;
                dist[nx]=dist[start]+1;//방문할 시에만 레벨 누적해준다
                }
                
            if(nx==goal)
                return;
        }
        q.pop();

    }

}

int main(){
    int N, K;//위치 입력 받기
    cin>>N>>K;
    if(N==K){
        cout<<"0";
        return 0;
    }

    BFS(N, K);
    cout<<dist[K];

}