[BOJ G5][C++] 백준 13549번 : 숨바꼭질 3 (런타임에러와의전쟁)

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

13549번: 숨바꼭질 3

 

문제

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

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

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

풀이

BFS 를 일차원 버전으로 돌리는거라는 점은 달라지지 않는다.

다만 위에 시행착오처럼 정답이 최솟값이 나올 수 있도록 우선순위만 잘 설정해주자

 

// Authored by : seondal
// 풀이 : https://whkakrkr.tistory.com/
// Co-authored by : -

//#include <bits/stdc++.h>
#include <iostream>
#include <queue>

using namespace std;

int n,k;
int dis[200002];
queue<int> q;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    for(int i=0; i<200000; i++) dis[i] = -1;
    
    cin >> n >> k;
    q.push(n);
    dis[n] = 0;
    
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        
        // 순간이동
        if(cur*2 < 200000 and dis[cur*2] == -1) {
            dis[cur*2] = dis[cur];
            q.push(cur*2);
        }
        
        for(int i=0; i<2; i++){
            int next=0;

            if(i==0) next = cur-1;
            else if(i==1) next = cur+1;

            if(next<0 or next>=200000) continue;
            if(dis[next] != -1) continue;

            dis[next] = dis[cur]+1;
            q.push(next);
        }
    }
    
    cout << dis[k];
}

/*
 */

 

---

시행착오

처음에는 BFS 를 1차원 수직선으로 돌리면 되겠구나 하고 편하게 풀었다.

    while(!q.empty()){
        int cur = q.front();
        q.pop();
        
        for(int dir=0; dir<3; dir++){
            int next;
            if(dir==0) next = cur+1;
            else if(dir==1) next = cur-1;
            else next = cur*2;
            
            // 답이 나왔다!
            if(next==k) {
                cout << dis[cur]+1;
                return 0;
            }
            
            if(next<0 || next>=200002) continue; // 범위를 넘어섰다면
            if(dis[next] != -1) continue;  // 이미 방문 했다면

            if(dir==2) dis[next] = dis[cur]; // 순간이동
            else dis[next] = dis[cur] + 1;  // 걷기
            
            q.push(next);
        }
        }

그런데 틀렸습니다가 뜨는것이다..

 

그런데 정말 운좋게도 딱 내 문제점을 짚어주는 질의응답 이 있었다.

https://www.acmicpc.net/board/view/81912

글 읽기 - 어느부분에서 틀린건지 도저히 찾지 못하겠습니다..

 

반례

4 6

오답 : 2
정답 : 1

 

그렇다.

시간을 최소화해야하기 때문에

순간이동을 우선적으로 해야하는것

 

시행착오 2

 

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

지옥의 OutOfBounds ..

범위도 잘 정해주고 조건도 잘 정했는데 왜 뜨는지 정말 궁금했다

 

if(dis[cur*2] == -1 and cur*2 < 200000) {
            dis[cur*2] = dis[cur];
            q.push(cur*2);
        }

원인 찾음...

쇼트서킷ㅠㅠㅠㅠㅠㅠㅠㅠ

 

if절에서 조건이 여러개면 앞 조건을 먼저 수행하고

해당 조건이 true 이면 뒤에 조건을 확인

해당 조건이 false 이면 뒤에 조건을 확인하지도 않고 그냥 넘어간다

 

그렇다.. dis[cur*2] 에서 범위를 넘어버리니 런타임에러가 발생한것...

확인을.. 잘하자 ㅠㅠㅠㅠㅠㅠ