Gidhub BE Developer

[BOJ] 12851. 숨바꼭질2

2018-09-21
goodGid
Algorithm

Problem

Problem URL : 숨바꼭질2

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

#include <iostream>
#include <queue>
using namespace std;

int visit[100001];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int st,dest;
    cin >> st >> dest;
    
    if( st == dest ){
        // [1]
        cout << "0" << '\n' << "1" << endl;
        return 0;
    }
    
    queue<int> q;
    q.push(st);
    
    int time = -1;
    int flag = 0;

    while (! q.empty()) {
        if( flag )
            break;
        
        time ++;
        int size = (int) q.size();
        
        for(int i=0; i<size; i++){
            int top = q.front();
            q.pop();
            
            if( top == dest ){
                flag ++;
                continue;
            }
    
            /*
             // [2]
            if( visit[top] ) // Already Visit
                continue;
            */

            visit[top] = 1;
            
            if( top - 1 >= 0 && !visit[top - 1] )  // Already Visit
                q.push(top - 1);
            
            if(top + 1 <= 100000 && !visit[top + 1] )  // Already Visit
                q.push(top + 1);
            
            if(top * 2 <= 100000 && !visit[top * 2] )  // Already Visit
                q.push(top * 2);
            
        } // end of for i
    } // end of while
    
    if( flag )
        cout << time << endl << flag << endl;
    
    return 0;
}

Review

  • 시작점과 도착점이 같으면 0초인데 나는 1초로 해서 1시간 넘게 삽질했다.

  • 문제를 똑바로 읽자 !!!

  • [2]을 넣게되면 다음과 같은 경우 틀리게 된다.

1 4 일 때

1 2 4
 + x
1 2 4
 x x

/*
+로 된 2 값과
x로 된 2 값은 
경로가 다르기 때문에 따로 처리해줘야한다.
하지만 [2] 주석을 풀게되면
+로 된 2를 먼저 처리하게되면
x로 된 2는 continue가 되어 문제가 발생한다.
*/

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

#include <iostream>
#include <queue>
#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);
    
    int st, dest;
    cin >> st >> dest;

    queue<p> q;
    q.push({st,0});

    int ans = 0;
    int ans_time = 2e9;
    while (! q.empty()) {
        int top = q.front().first;
        int time = q.front().second;
        q.pop();
        if( time > ans_time )
            break;
        
        if(top == dest){
            ans_time = time;
            ans++;
            continue;
        }
        v[top] = 1;
        if( top + 1 < 100001 && !v[top+1] ){
            q.push({top+1, time+1});
        }
        if( top - 1 > -1 && !v[top-1]){
            q.push({top-1, time+1});
        }
        if( top * 2 < 100001 && !v[top*2]){
            q.push({top*2, time+1});
        }
    }
    cout << ans_time << endl;
    cout << ans << endl;
    return 0;
}

Review

if( time > ans_time )
    break;

 if(top == dest){
    ans_time = time;
    ans++;
    continue;
}

  • 문제가 요구하는 조건은 최단 시간과 최단 시간내 목적지까지 가는 경로의 수 이다.

  • 그렇기 때문에 최단 시간 이후에 경우에 대해서는 볼 필요가 없다.

  • 가지치기를 하기 위한 방법으로 현재 보는 시간(=time)이
    이전에 목적지에 도달하여 재초기화된 시간(=ans_time)보다 클 경우에 Loop를 Break했다.

  • 이 조건이 가능한 이유는 다음 레벨의 값을 볼 때
    이미 이전에 도착점에 도착한 경우가 있다면
    정답의 레벨(=ans)은 현재 체크하려는 값의 레벨보다 낮을 것이다.
    그렇게 되면 현재 체크하는 값이 목적지에 갈 수 있더라도 최단 시간이 될 수 없기 때문에 Loop를 탈출시켜도 된다.

  • 또한 같은 레벨에 대해서는
    목적지에 도달하여 ans_time 값이 초기화되더라도
    그 값은 같은 레벨에 대해서는 모두 같기 때문에 if( time > ans_time ) 종료 조건에 빠지지 않는다.

  • 즉 queue에 있는 같은 레벨에 모든 경우의 수를 체크 수 있게 된다.

1 -> 4 로 가는 경우라면

1 (+) 2 (+) 3
1 (+) 2 (*) 4
1 (*) 2 (+) 3
1 (*) 2 (*) 4 경우가 나올 수 있다.

이 때 
Tree 구조로 생각하면
          1
    2             2 
3(1) 4(1)     3(2) 4(2)

각 행에 끝에 있는
3(1) 4(1) 3(2) 4(2) 는 같은 레벨이다.

처음에 3(1)을 볼 땐 목적지가 아니기 때문에 
3(1)이 갈 수 있는 3가지 조건에 대해 queue에 push를 해준다.
그리고 4(1)를 보면 목적지이기 때문에
ans_time을 2로 초기화해주고 ans++를 해준다. 

그리고 continue이기 때문에 queue에서 pop을 해주면 3(2)이 나오게 된다.

이 때는 같은 레벨이기 때문에 
if( time > ans_time ) 조건을 pass하게 되고 
3(1)과 마찬가지로 갈 수 있는 3가지 경우를 queue에 push해준다.

그리고 4(2)를 pop하고 다시 ans_time을 2로 초기화해주고 ans++를 해준다.
여기까지 같은 레벨에 대한 체크가 끝났다.

이제 pop을 하는 값은 레벨이 다른 상태이고
그말은 목적지까지 도달할 수 있는 경우라 하더라도
기존에 답보다는 무조건 크게 된다.

그렇기 때문에 체크를 할 필요도 없이
if( time > ans_time ) 조건에 의해 while문을 빠져나간다.

Recommend

Index