13913 숨바꼭질 4 : bfs

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

13913번: 숨바꼭질 4

 

문제요약

1칸 좌우 이동, 2배 이동이 가능할 때, 도착점으로 가는 최단 시간과 궤적 나타내기

 

난이도

Gold 4

---

풀이 포인트

• prev에 계속 쌓아두며 역추적해가는 방법
• for문 사용법

   for (int next : {now - 1, now + 1, now * 2})

---

REVIEW



우선 너무 오랜만에 풀어서 using namespace std 구문도 낯설어질 뻔 했다.

bfs의 기본 용법을 따르되 for문으로 재귀 스럽게 +1, -1, *2를 구현하는 방법과,

prev에 전 위치를 기록해 두고, 거슬러가며 for문을 돌리는 방법 등을 잘 익혀야 한다. 

---

CODE

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

// 경로 추적은 prev

#define prev aaa
#define next aaaa

const int max_n = 200004;

int visited[max_n], prev[max_n], ret,here, cnt, next;
int n, k;

vector<int> v;
queue<int> q;

int main(){
    cin >> n >> k;
    visited[n] = 1;
    q.push(n);

    while(q.size()){
        here = q.front();
        //cout << "현재 here는 " << here <<'\n';
        q.pop();

        if(here == k){
            //cout << "도착지에 도달했다"<<'\n';
            ret = visited[k];
            break;
        }

        for(int next: {here + 1, here - 1, here * 2}){


            if(next >= max_n || next < 0 || visited[next]) continue;
            //cout << "현재 next는 "<< next <<" 처음 방문했다."<<'\n';

            visited[next] = visited[here] + 1;

            //다음을 넣으면 그 전의 발자취가 나오는!
            prev[next] = here;
            q.push(next);
        }
    }

    // 거슬러 올라감.
    for(int i = k; i != n; i = prev[i]){
       // cout << "현재 i는 " << i << '\n';
        v.push_back(i);
    }

    v.push_back(n);
    cout << ret -1 << '\n';

    reverse(v.begin(), v.end());
    for(int i : v) cout << i << ' ';
    return 0;

}