Gidhub BE Developer

[BOJ] 13913. 숨바꼭질4

2018-09-23
goodGid

Problem

Problem URL : 숨바꼭질4


[1] Answer Code (18. 09. 23)

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#define p pair<int,int>
using namespace std;

int v[100001]; // v is visit

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    memset(v,-1,sizeof(v));
    int st, dest;
    cin >> st >> dest;
    
    queue<p> q;
    q.push({st,0});
    v[st] = 1;
    
    while (! q.empty()) {
        int top = q.front().first;
        int time = q.front().second;
        q.pop();
        
        if(top == dest){
            cout << time << endl;
            break;
        }
        
        if( top + 1 < 100001 && v[top+1] == -1){
            v[top+1] = top;
            q.push({top+1, time+1});
        }
        if( top - 1 > -1 && v[top-1] == -1){
            v[top-1] = top;
            q.push({top-1, time+1});
        }
        if( top * 2 < 100001 && v[top*2] == -1){
            v[top*2] = top;
            q.push({top*2, time+1});
        }
    }
    
    vector<int> _v;
    _v.push_back(dest);
    while (dest != st) {
        _v.push_back(v[dest]);
        dest = v[dest];
    }
    
    for(int i=(int)_v.size()-1; i>=0; i--)
        cout << _v[i] << " ";
    return 0;
}

Review

  • 경로를 저장하는게 까다로웠다.

  • 경로를 추적하는 방법은 아래와 같다.

만약 답이
1 2 4 라면
v[4] = 2
v[2] = 1 처럼 경로를 저장한다.


  • 눈으로 봤을 땐 다를게 없는데 자꾸 메모리 초과가 뜨는 문제가 발생했다.

  • 메모리 초과가 뜨고

  • 이렇게 해야 맞았다.

  • 1시간 정도 삽질을 한 끝에 문제를 발견했다.

  • 그 이유는 시작점과 목적지가 같았을 경우 첫 번째는 무한 루프를 돌게 된다. 시작점과 목적지가 (1,1)을 제외한 경우


Comments

Content