#1697번 숨바꼭질 (C++)

링크 : www.acmicpc.net/problem/1697

1697번: 숨바꼭질

문제풀이는 다음과 같다. 

(1) 최초의 시작점을 입력받고, 해당 시작지점을 큐에 넣어준다.

(2) 큐에 맨 앞 값을 temp라 지정한다. 그리고 큐의 값을 한 번 pop해준다.

 

이제부터 temp는 현재 위치를, pos는 +1, -1, *2를 하는 것에 따라 달라지는 위치값이라고 생각해야한다. 

 

(3) temp 값의 -1, +1, *2의 값을 순차적으로 for문으로 구해준 뒤 그 값을 pos에 넣는다.

(4) 이때 한 번의 계산이 이루어질때마다 계산 결과값(pos)이 목표지점에 도달하는지를 체크한다 -> else if(pos==m)

도달할 경우 이전 횟수에 +1을 추가하려 출력한 뒤 종료한다.
(5) 그렇지 않을 경우, 계산 결과값(pos)에 방문한 적이 있는지를 체크하고, 방문한 적이 없을 경우-> else if(ch[pos]==0)

해당 pos값에는 temp의 누적 계산횟수에 +1을 더하여 기록한다. 그리고 pos값을 큐에 넣어준다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n = 0, m = 0, pos = 0, temp = 0;
int mv[3] = {-1,1,0};
int arr[100001];
int ch[100001] = {0,};

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    if(n==m) {
        cout << 0 << "\n";
        exit(0);
    }
    queue<int> q;
    q.push(n);
    while(!q.empty()){
        temp = q.front();
        q.pop();
        for(int i=0; i<3; i++){
            if(i==2){
                pos = temp*2;
            }
            else pos = temp+mv[i];
            if(pos>100000);
            else if(pos==m){
                cout << ch[temp] + 1 << "\n";
                exit(0);
            }
            else if(ch[pos]==0){
                ch[pos] = ch[temp]+1;
                q.push(pos);
            }
        }
    }

    return 0;
}

 

유의해야할 점은 if(pos>100000); 부분인데, 최대 거리값 100000을 넘어갈 경우 배열의 범위를 초과하는 관계로

아무것도 하지 않고 그저 큐의 값만 pop한 체로 종료해야 오류를 겪지 않는다. 

 

오버플로우를 간과한 덕에 틀렸습니다를 겪게 되었다.