BOJ -1697 ) 숨바꼭질

 

 

---

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

1697번: 숨바꼭질

#include <iostream>
#include <queue>
using namespace std;
int N, K, time;
bool visit[100001];
typedef struct {
    int now, time;
 
}pos;
int main(void) {
    cin >> N >> K;
    if (K < N) {
        cout << N - K;
    }
    else if (N == K) {
        cout << 0;
    }
    else {
 
        pos start = { N , 0 };
        queue < pos > Q;
        Q.push(start);
        int now = N;
        while (!Q.empty()) {
 
            now = Q.front().now;
            time = Q.front().time;
            if (now == K) break;
            Q.pop();
 
            if (now + 1 <= 100000 && !visit[now + 1]) {
                visit[now + 1] = true;
                Q.push({ now + 1 , time + 1 });
            }
            if (2 * now <= 100000 && !visit[2 * now]) {
 
                visit[2 * now] = true;
                Q.push({ 2 * now , time + 1 });
            }
            if (now - 1 >= 0 && !visit[now - 1]) {
                visit[now - 1] = true;
                Q.push({ now - 1 , time + 1 });
 
            }
 
        }
        cout << time;
 
 
 
 
    }
 
 
    return 0;
}

---

 

 

---

간단하게 풀릴줄 알았는데 

 

메모리 초과를 받았었다. Q에 많이 넣어서 날수도 있겠다고 생각했었는데,

 

어떤 한 위치에 대해서 여러번 큐에 들어갈 수 있기에 visit 배열을 100001 크기로 잡아주어서 

 

실행하였더니 런타임 에러가 났다.

 

즉 테스트케이스를 넣어볼때에 2 * now 의 값이 100000을 넘는경우도 포함된다는 말이였다.

 

if( visit[ 2 * now ] && 2 * now <= 100001)

위의 경우는 런타임 에러가 나지만

if( 2 * now <= 100001 && visit[ 2 * now ])

이 경우는 나지 않는다.

 

즉 배열의 인덱스값을 확인하는 과정에서 now의 범위 체크를 먼저 해주고 배열을 찾아가야지만 항상 유효한 인덱스에 

 

접근할 수 있다.

 

배열 인덱스를 참고할 때에 이러한 부분을 기억해야겠다.