[백준] 13913 숨바꼭질 4 C++

1. 문제 설명

• 링크 : https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

---

2. 풀이 과정

• 문제 해결의 흐름 
  1.  '1697 숨바꼭질' 문제와 같은 방법으로 최단 시간을 출력하자.
  2. ⭐️ 최단 시간까지의 이동 과정은 어떻게 저장할 것인가?? memo라는 int형 배열을 만들어준 뒤 memo[next_position] = cur_position을 통해 현재 위치 값을 저장해 주자. 
  3.  문제 조건을 만족하는 position이 result_position이라 하였을 때 result_position = memo[result_position]을 통해 이전 위치 정보를 result_position에 담을 수 있다. 이 방법으로 이동 과정을 출력하자.
• 나의 코드 

#include <iostream>
#include <queue>

using namespace std;

#define MAX 100001

int N, K; // N : 수빈이의 위치, K : 동생의 위치
int visited[MAX] = {}; // 전부 0으로 초기화
int memo[MAX]; // 연산 과정 저장할 배열
vector<int> ans_vector; // 어떻게 이동하는지 저장하는 vector

void bfs() {
    queue<int> q;
    q.push(N);

    while (!q.empty()) {
        int curPosition = q.front();
        q.pop();

        // 동생 찾았다면??
        if (curPosition == K) {
            int i = curPosition; // 현재 위치 K

            while(i != N) {
                ans_vector.push_back(i);
                i = memo[i]; // i = 이전 위치
            }
            ans_vector.push_back(i); // i == N

            break;
        }

        int minusPosition = curPosition - 1;
        int plusPosition = curPosition + 1;
        int multiPosition = curPosition * 2;

        // 1. -1
        if (minusPosition >= 0 && visited[minusPosition] == 0) {
            q.push(minusPosition);
            memo[minusPosition] = curPosition;  // ⭐️ 나중 위치 인덱스가 현재 위치 값을 저장한다 !!
            visited[minusPosition] = visited[curPosition] + 1;
        }

        // 2. + 1
        if (plusPosition < MAX && !visited[plusPosition]){
            q.push(plusPosition);
            memo[plusPosition] = curPosition;
            visited[plusPosition] = visited[curPosition] + 1;
        }

        // 3. * 2
        if (multiPosition < MAX && !visited[multiPosition]) {
            q.push(multiPosition);
            memo[multiPosition] = curPosition;
            visited[multiPosition] = visited[curPosition] + 1;
        }
    }

    cout << visited[K] << endl; // 최단 시간 출력
    for (int i = visited[K]; i >= 0; i--) { // 이동 과정 공백 포함해서 출력
        cout << ans_vector[i] << " ";
    }

}

int main() {
    cin >> N >> K; // 입력 받기
    bfs();

    return 0;
}

 

• 이 문제를 통해 얻어갈 수 있는 것들
  •  memo 배열을 통해 이동과정을 저장할 수 있었다. 유용한 방법이니 자주 사용할듯?

---

3. 후기 

 꽤나 신박한 방법을 찾은 듯