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

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

1697번: 숨바꼭질

 본 문제는 USACO US Open 2007 Contest Silver 2번 문제다. 대부분 이런 문제들은 거리를 계산하는 배열과 방문을 확인하는 bool 배열을 선언한다. 그런데 이번 문제에서 보면 방문 확인 배열을 선언하지 않고 풀 수 있다. 그러나 메모리를 줄이고자 했던 일이 작은 실수로 문제를 푸는 시간을 증가하는 일이 발생할 수 있다. 사실 내가 한 실수다. 코딩 절차는 다음과 같다.

1. 범위 확인 및 방문 여부 확인
2. 가능할 때, queue에 push ( ※ 초기값 방문에 대한 실수를 조심하자!)

#include <cstdio>
#include <queue>
 
using namespace std;
 
int main() {
    int d[200001] = {0};
    int n, m;
    scanf("%d %d", &n, &m);
    queue<int> q;
    q.push(n);
    d[n] = 1; // 초기값 방문 여부를 위해 인위적으로 1 증가
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        // 뒤로 한 칸 갈 경우
        if (now-1 >= 0 && d[now-1] == 0) {
            d[now-1] = d[now] + 1;
            q.push(now-1);
        }
        // 앞으로 한 칸 갈 경우
        if (now+1 <= 200000 && d[now+1] == 0) {
            d[now+1] = d[now] + 1;
            q.push(now+1);
        }
        // 순간이동 할 경우
        if (now*2 <= 200000 && d[now*2] == 0) {
            d[now*2] = d[now] + 1;
            q.push(now*2);
        }        
    }
    // 인위적으로 1을 증가하였기 때문에 -1
    printf("%d", d[m]-1);
    return 0;
}