BOJ 1697 숨바꼭질

코딩 15분, 디버깅 1시간

 - STL은 잘못이 없다.

 

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

1697번: 숨바꼭질

 

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int N,K;
int d[] = {1,-1};

int main() {
    int visited[100002];
    memset(visited,0,sizeof(visited));
    
    scanf("%d%d",&N,&K);
    queue<int> Q;
    Q.push(N);
    while(!Q.empty()) {
        int tmp=Q.front();
        Q.pop();
        if(tmp == K) {
            cout << visited[tmp];
            return 0;
        }
        for(int i=0;i<3;++i) {
            int nP;
            if(i==2) nP = 2*tmp; // 여기!
            else nP = tmp+d[i];
            if((nP>=0&&nP<=100000)&&(visited[nP]==0||visited[nP]>visited[tmp]+1)) {
                Q.push(nP);
                visited[nP] = visited[tmp]+1;
            }
        }

    }
}

며칠째 보는 BFS문제이다. 반 기계적으로 BFS 탐색 코드가 나왔는데 어이없게도 런타임 에러가 발생했다;;

 

자주 그렇듯 메모리 접근 오류라 직감했고, 배열 범위 체크 이외에는 메모리 오류가 발생할 일이 없다고 생각해  Short Circuit 이 발생했나 살펴봤지만, 늘 유의하며 코드를 작성하기에 당연하게도 Short Circuit 문제는 아니었다. 

사실문제는 다른데 있었다.

 

주석 달린 위치에서

int nP = tmp + d[i];
...
if(i==2) nP = 2 * tmp;

d[i]가 문제였다. 전혀 신경을 못쓰고 있었는데 전역 d[] 배열의 범위를 넘어버린 것이다. 이런 사소한 문제 때문에 1시간이나 소비했다니.. 사실 이전에도 여러 번 런타임 에러가 발생해 포기한 문제가 있었는데 아마 이번 경우와 마찬가지로 신경 쓰지 못한 곳에서 배열 범위 초과가 일어났던 것 같다.