13913번: 숨바꼭질 4

숨바꼭질 4 

스페셜 저지

 

시간 제한           메모리 제한                     제출                            정답맞힌 사람             정답                         비율

 

2 초

512 MB

32257

10834

7630

31.590%

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

예제 입력 1 복사

5 17

예제 출력 1 복사

4
5 10 9 18 17

예제 입력 2 복사

5 17

예제 출력 2 복사

4
5 4 8 16 17

 

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

13913번: 숨바꼭질 4

 

흐름

맞은 코드

#include <bits/stdc++.h>
using namespace std;
#define prev mae

const int MAX = 200000;
int n,k, visited[MAX+4], prev[MAX+4];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n >> k;
    //2. bfs 수행
    queue<int> q;
    q.push(n);
    visited[n]=1;
    prev[n]=-1; //루트
    while(q.size()){
        int now = q.front(); q.pop();
        for(int next:{now-1, now+1, now*2}){
            if(0<=next && next<=MAX){
                if(!visited[next]){
                    visited[next]=visited[now]+1;
                    q.push(next);
                    prev[next]=now; //부모 노드 저장
                }
            }
        }
    }
    //3. 가장 빠른 시간 출력
    cout << visited[k]-1 <<"\n";
    //4. 경로 저장(자식->부모 순으로 저장하므로 스택을 이용해 반대로 출력되도록 하기)
    stack<int > s;
    int now=k;
    s.push(k);
    while(now!=n){
        int p = prev[now];
        s.push(p);
        now=p;
    }
    //5. 경로 출력하기
    while (s.size()){
        cout << s.top()<<" "; s.pop();
    }
    cout <<"\n";
    return 0;
}

 

최단 경로 출력하기(경로 추적)

for(int next:{now-1, now+1, now*2}){
    if(0<=next && next<=MAX){
        if(!visited[next]){
            visited[next]=visited[now]+1;
            q.push(next);
            prev[next]=now;
        }
    }
}

각 위치에 대해 부모 노드를 저장하면 최단 경로를 출력할 수 있다.

경로 출력시 prev 배열 사용하기! => prev[next]=here;

 

유의할 점

puts함수와 cout 함수를 같이 썼는데  정답과 출력값은 같지만 자꾸 틀렸다고 나왔다.!

결국 cout만 쓰거나 puts 함수만 쓰거나 둘 중 하나만 선택해서 써야할 것 같다! (puts은 문자열 출력만 가능하므로 cout 위주로 쓰자.)

 

선생님 코드

#include <bits/stdc++.h>
using namespace std;

#define prev aaa
const int MAX = 200004;
int n,k, visited[MAX], prev[MAX], here,ret;
queue<int> q;
vector<int> v;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력하기
    cin >> n >> k;
    //2. bfs 수행
    visited[n]=1;
    q.push(n);
    while(q.size()){
        here = q.front(); q.pop();
        if(here==k){ //동생 위치(k)에 도착하면 break(가지치기)
            ret = visited[k];
            break;
        }
        for(int next:{here-1, here+1, here*2}){
            if(next<0 || next>=MAX || visited[next]) continue;
            visited[next]=visited[here]+1;
            prev[next]=here;
            q.push(next);
        }
    }
    //3. 경로 벡터에 저장하고 역으로 만들기
    for(int i=k;i!=n;i=prev[i]){
        v.push_back(i);
    }
    v.push_back(n);
    reverse(v.begin(), v.end());
    //4. 정답 출력하기
    cout << visited[k]-1 << "\n";
    for(int i:v){
        cout << i << " ";
    }
    return 0;
}

 

내 코드와 다른점

• 나는 입력값을 반대로 출력하기위해 스택을 사용했지만, 선생님은 벡터에 저장하여 reverse 함수👍를 사용했다.
  • 벡터와 스택을 비교했을때, 알고리즘 풀 때 벡터를 더 많이 사용한다. 스택은 가독성이 좋으나  top이 아닌 원소는 접근할 수 없어 디버깅이 불가능하고, 개별 원소에 index로 접근이 불가능하기 때문이다.
  • 출처: https://dev-jhl.tistory.com/entry/c-%EC%8A%A4%ED%83%9D-vs-%EB%B2%A1%ED%84%B0

c++ 스택 vs 벡터

 

• 나는 bfs시에 모든 원소의 최단경로 값을 구하여 동생 위치의 최단경로 값을 "조회" 했지만, 선생님은 동생 위치를 넘어선 값을 계산하지 않게 하기위해 가지치기👍를 했다. => break 이용 (return은 main함수 자체를 끝내므로 break를 사용하자.)