[C++][백준 13913] 숨바꼭질 4

[문제]

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

13913번: 숨바꼭질 4

[풀이 과정]

처음엔 vector<int> subin[100000] 을 이용해서 다음 수빈이의 위치에 현재까지 왔던 수빈이의 위치좌표들을 저장하게 만들었엇다.

하지만 해당 방식을 이용하니 메모리 초과가 일어났다.

그래서 수빈이가 가는 다음 위치에 현재 수빈이의 위치를 담아두고 마지막에 solution함수가 끝나면 동생의 위치 k부터 수빈이의 위치까지 돌아가게 만들었다.

 

*주의사항 : 오랜만에 코드를 짜다가 if(조건1 && 조건 2) 에서 조건1이 먼저 일어나고 조건2가 일어난다는 점에 대해서 주의가 부족했다.

덕분에 왜 코드에서 런타임 에러가 나는지 한참동안 찾다가 마지막에서야 눈치를 챌 수 있었다. 사소한 디테일을 놓치지 말자.

[코드]

<처음 코드>

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> subin[100001];
int visited[100001];

void solution(int n, int k){


    queue<int> count;
    count.push(n);

    while(count.size() > 0){

        int curSubin = count.front();
        count.pop();
        visited[curSubin] = 1;

        // cout<<"curSubin : "<<curSubin<<endl;

        if(visited[curSubin * 2] == 0){
            if(curSubin * 2 <= 100000){
                subin[curSubin * 2] = subin[curSubin];
                subin[curSubin * 2].push_back(curSubin);
                visited[curSubin * 2] = 1;
                count.push(curSubin * 2);

                if(curSubin * 2 == k){
                    break;
                }
            }
        }

        if(curSubin + 1 <= 100000 && visited[curSubin + 1] == 0){
            subin[curSubin + 1] = subin[curSubin];
            subin[curSubin + 1].push_back(curSubin);
            visited[curSubin + 1] = 1;
            count.push(curSubin + 1);

            if(curSubin + 1 == k){
                break;
            }
        }

        if(curSubin - 1 >= 0 && visited[curSubin - 1] == 0){
            subin[curSubin - 1] = subin[curSubin];
            subin[curSubin - 1].push_back(curSubin);
            visited[curSubin - 1] = 1;
            count.push(curSubin - 1);

            if(curSubin - 1 == k){
                break;
            }
        }
    }

    return;
}


int main(){
    //n은 수빈이 위치, k는 동생 위치.
    int n,k;
    cin>>n>>k;

    solution(n,k);

    cout<<subin[k].size()<<endl;
    for(int i = 0;i<subin[k].size();i++){
        cout<<subin[k][i]<<" ";
    }
    cout<<k<<endl;



    return 0;
}

 

<정답 코드>

#include <iostream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

int subin[100001];
int visited[100001];

void solution(int n, int k){

    //수빈이의 위치를 닮을 queue
    queue<int> count;
    count.push(n);
    visited[n] = 1;

    while(count.size() > 0){

        int curSubin = count.front();
        count.pop();

        //차례대로 수빈이가 이동하는 위치이며
        //if문을 통해서 갈수있는 곳인지 파악
        //visited를 이용해서 방문을 표시
        //subin이의 다음 좌표에 현재 위치 넣기.
        //queue에 수빈이의 다음 좌표 넣기.
        //만일 다음 좌표가 k라면 탈출.

        if(curSubin * 2 <= 100000 && visited[curSubin * 2] == 0){
            visited[curSubin * 2] = 1;
            subin[curSubin * 2] = curSubin;
            count.push(curSubin * 2);
            if(curSubin * 2 == k){
                return;
            }
        }
        if(curSubin + 1 <= 100000 && visited[curSubin + 1] == 0){
            visited[curSubin + 1] = 1;
            subin[curSubin + 1] = curSubin;
            count.push(curSubin + 1);
            if(curSubin + 1 == k){
                return;
            }
        }
        if(curSubin - 1 >= 0 && visited[curSubin - 1] == 0){
            visited[curSubin - 1] = 1;
            subin[curSubin - 1] = curSubin;
            count.push(curSubin - 1);
            if(curSubin - 1 == k){
                return;
            }
        }
    }

    return;
}


int main(){
    //n은 수빈이 위치, k는 동생 위치.
    int n,k;
    cin>>n>>k;

    solution(n,k);

    stack<int> answer;

    int locate = k;

    //locate가 n이 오기 전까지
    while(locate != n){
        //locate는 왔던 좌표로 이동한다.
        locate = subin[locate];
        //stack에 차례대로 담자.
        answer.push(locate);
    }

    cout<<answer.size()<<endl;

    while(answer.size() > 0){
        cout<<answer.top()<<" ";
        answer.pop();
    }
    cout<<k<<endl;

    return 0;
}