[백준 1697] 알고리즘 87일차 : 숨바꼭질

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

C++ BFS

수빈이가 동생이 있는 좌표까지 가는데 걸리는 최단시간을 구하는 문제이다. 수빈이는 1초에 앞,뒤,2배만큼 이동할 수 있고

최소한 몇초만에 찾는지 구하는 문제

 

접근방법

인접한 노드를 현위치에서 -1, +1, *2 위치로 생각하고

distances배열에 최단거리를 저장하면서 BFS 최단거리 문제로 풀었다.

 

오답노트

큐에 push할때 배열의 최대 범위를 넘어나서 런타임에러가 났었다. 푸시할때 조건 추가해서 해결

 

소스코드

#include <iostream>
#include <queue>
using namespace std;
int distances[100001];
bool visit[100001];
queue<int> q;

int main(){
    int x,k;
    cin >> x >> k;
    q.push(x);
    visit[x] = true;
    while(!q.empty() && !visit[k]){
        int here = q.front();
        q.pop();
        if(here-1 >= 0 && !visit[here-1] && here-1 <= 100001){
            q.push(here-1);
            visit[here-1] = true;
            distances[here-1] = distances[here] + 1;
        }
        if(!visit[here+1] && here+1 <= 100001){
            q.push(here+1);
            visit[here+1] = true;
            distances[here+1] = distances[here] + 1;
        }
        if(!visit[here*2] && here*2 <= 100001){
            q.push(here*2);
            visit[here*2] = true;
            distances[here*2] = distances[here] + 1;
        }
    }
    cout << distances[k];
    return 0;
}