[C++] 백준 1697 - 숨바꼭질

백준 1697 : 숨바꼭질

난이도 : 실버 1

시간 : 35분 소요

 

 

문제

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

1697번: 숨바꼭질

풀이 과정

bfs를 사용해서 3가지 경우의 수를 검사한다.

1. -1 이동

2. +1 이동

3. x2 이동

 

 

처음에는 1, 3, 9, 27 마다 cnt를 1씩 높이려고 했는데 N에 따라 큐에 들어가는 수의 갯수가 달라져 cnt 값이 정상적으로 출력되지 않았다.

그래서 pair 자료형을 사용하였고, 큐에 들어가는 수에 cnt 값을 같이 저장했다.

 

그럼에도 실패하였다. 그래서 도저히 잘못된 걸 찾지 못해서 조금 헤맸다.

그러던 중 문득 입력값으로 두 값이 동일할 때 어떨지 확인해봤고, 문제를 찾을 수 있었다.

출발점을 d[N] = 1 로 설정하여서 동일한 값이면 마지막에 d[K]를 출력할 때 1를 출력했다.

그래서 d[N] = 0 으로 설정하니 성공하였다.

 

 

최종 코드

#include <iostream>
#include <queue>
#define MAX 100001
using namespace::std;

int N, K;
int d[MAX];

void bfs(){
    d[N] = 0;
    queue<pair<int, int>> q;
    q.push({N, 0});
    
    
    while(!q.empty()){
        int t = q.front().first;
        int cnt = q.front().second;
        q.pop();
        
        int tmp[3] = {t-1, t+1, 2*t};
        
        if(t == K){
            break;
        }
        
        for(int i=0; i<3; i++){
            if(tmp[i]>=0 && tmp[i]<=100000){
                if(d[tmp[i]] == 0){
                    d[tmp[i]] = cnt+1;
                    q.push({tmp[i], cnt+1});
                }
            }
        }
    }
}

int main(){
    scanf("%d %d", &N, &K);
    
    bfs();
    printf("%d\n", d[K]);
}