백준 13549 - 숨바꼭질 3

문제 : https://www.acmicpc.net/problem/13549

 

풀이과정

현재 위치 (N) 에서 -> 목적지 (K) 까지 도달하는 가장 빠른 시간을 구하는 문제이다.

걸리는 시간, 즉 가중치가 1 또는 0 이므로 0-1너비우선탐색 을 사용하여 풀이할 수 있다. 

 

풀이

1. 0초 후 2*X로 이동하는 것이 가능하기 때문에

너비우선탐색 시 2*X의 경우 push_front를 통해 가장 먼저 탐색할 수 있도록 한다.

 

2. 1초 후 X-1 또는 X+1 로 이동할 수 있으며, 0초보다 오래 걸리기 때문에

너비우선탐색 시 push_back을 통해 나중에 탐색하도록 한다.

 

위 과정을 반복하면 최소 시간을 구할 수 있다.

 

코드

#include <iostream>
#include <stdio.h>
#include <deque>
using namespace std;

int N,K;
int visited[100001];
deque < pair < int,int > > dq;

void solution(int start) {
    visited[start] = 1;
    dq.push_back({start,0});
    while(!dq.empty()) {
        int now = dq.front().first;
        int dist = dq.front().second;
        if(now == K) {
            printf("%d\n",dist);
            return;
        }
        dq.pop_front();

        // x*2
        if(now*2 <= 100000 && visited[now*2] == 0) {
            dq.push_front({now*2,dist});
            visited[now*2] = 1;
        }
        // x-1
        if(now-1 >= 0 && visited[now-1] == 0) {
            dq.push_back({now-1,dist+1});
            visited[now-1] = 1;
        }
        // x+1
        if(now+1 <= 100000 && visited[now+1] == 0) {
            dq.push_back({now+1,dist+1});
            visited[now+1] = 1;
        }
        
    }
}

int main() {
    scanf("%d %d",&N,&K);
    solution(N);
}