[C++] 백준(BOJ) - 13913 : 숨바꼭질 4

27 Oct 2023 in Develop on C++, Algorithm Last modified at: 2023-10-28

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

백준(BOJ) - 13913 : 숨바꼭질 4(링크)

알고리즘

1. 그래프이론
2. BFS
3. 경로 추적 알고리즘
4. dequeue

풀이

1. 최단 거리 찾기 문제 - BFS
2. 경로 추적 알고리즘
   • 경로를 담을 prev 배열을 만들고
   • prev[next] = here 할당
   • dequeue를 이용해 prev[]을 끝에서 부터 담기

코드

// 13913 : 숨바꼭질 4
#include <bits/stdc++.h>
using namespace std;

const int MAX = 200002;
int n, k;
int visited[MAX+4], pos[MAX+4];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;

    queue<int> q;
    q.push(n);
    visited[n] = 1;
    pos[n] = n;

    while (q.size())
    {
        int now = q.front();
        q.pop();

        for (int next : {now - 1, now + 1, now * 2})
        {
            if (next <0 || next > MAX) continue;
            if (visited[next]) continue;

            visited[next] = visited[now] + 1;
            pos[next] = now; // 경로 추적을 위한 prev[next] = here
            q.push(next);
        }
    }

    cout << visited[k] - 1 << '\n';

	// deque를 활용하여 prev[] 배열 값을 deque에 옮겨 담기
    deque<int> dq = { k };
    while (dq.front() != n) dq.push_front(pos[dq.front()]);

    for (int i : dq) cout << i << ' ';

    return 0;
}

평가

• prev 값을 idx에 담으면서 prev 배열을 만들 수 있다
  • prev[next] = here 구조
• deque를 활용해 reverse 함수를 사용하지 않고 풀이 가능