백준 13549 숨박꼭질3 c++ [컴공과고씨]

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

13549번: 숨바꼭질 3

 

문제 간단 정리

수빈이는 일직성 상에 n이라는 점에 있고 동생은 k라는 점에 있다.

수빈이는 걷거나 순간이동을 하는데 위치가 x일때 걷는다면 1초 후 x-1 or x+1로 이동하고

순간이동하면 0초 후 2*x 만큼 이동할 때 동생을 찾을 수 있는 가장 빠른 시간을 구해라.

 

문제 해결 방법

저는 bfs를 통해서 해결해 주었습니다.

수빈이의 점에서 일직성 상 범위 내에서 x+1, x-1, 2*x와 걸린 초를 큐에 넣어 해결해 주는 방식입니다.

코드를 보면서 이해하면 쉽게 이해가 가능하고 bfs에 대해 잘 모르겠다면 밑 코드를 보면서  bfs가 어떤식으로 돌아가는지 

머리속에서 코드를 돌릴 수 있으면 bfs 문제가 나오면 쉽게 풀 수 있을 것이다.

 

전체 코드

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int n, k;
int vis[100003]; // 각 점에 도달하는 최단 시간을 기록
int result = 987654321; // 결과값
void bfs(int a){
    queue<pair<int, int>> q; // <위치, 시간>
    q.push(make_pair(a, 0)); // <초기위치, 0초>
    while(!q.empty()){
        int x = q.front().first; // 현재 위치
        int cnt = q.front().second; // 현재 위치까지 걸린 시간
        q.pop();
        if (x == k){ // 도착 지점 도달 시
            if(result > cnt) // 최단 시간일 경우 기록
                result = cnt;
        }else if (result < cnt){ // 기록된 결과을 넘은 시간인 경우 pass
            continue;
        }
        else{
            for (int i = -1; i <= 1;i++){ 
                int nx; // 다음 위치
                if (i == 0) // 순간이동한 경우
                    nx = 2 * x;
                else // 걷는 경우
                    nx = x + i;
            
                if(nx >= 0 && nx <= 100000){ // 일직성 상 범위 준수
                    // 순간이동을 하면 초가 변하지 않으므로 현재까지 걸린
                    // 시간이 다음 위치에 기록된 시간보다 적으면 
                    // 그것이 최단 시간이 됨.(-1 경우는 한번도 방문 안함)
                    if(i == 0 && (vis[nx] > cnt || vis[nx] == -1)){
                        q.push(make_pair(nx, cnt));
                        vis[nx] = cnt;
                    }// 걷는 경우 현재 시간에 +1 한 것이 더 작아야함.
                    else if(vis[nx] > cnt +1 || vis[nx]== -1){
                        q.push(make_pair(nx, cnt + 1));
                        vis[nx] = cnt + 1;
                    }
                }
            }
        }
    }
}
int main(){
    cin >> n >> k;
    memset(vis, -1, sizeof(vis)); // 0초인 경우도 있으니 -1로 초기화
    bfs(n);
    cout << result;
    return 0;
}