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

📌 문제

BOJ 바로가기

숨바꼭질 문제와 매우 유사하다. 차이점은 경로를 표시하는 출력을 추가해야 한다는 것뿐이다. 숨바꼭질 문제의 풀이는 다음 링크에서 확인할 수 있다.

[백준1697] 숨바꼭질 (C++)

🗡 풀이

📍 처음에는 배열 벡터를 선언해서 각 위치마다 이동경로를 표시해주었는데 메모리 초과가 떠서 실패했다.

📍 그래서 전략을 바꿔서 memo배열을 선언해준 다음 현재 위치 인덱스에 이전 위치 인덱스 정보를 담아주었다.
memo[nx] = n;
스택을 썼으면 더 편했을 것 같다ㅎㅎ

📍 수빈이의 위치와 동생의 위치가 같을 경우 위치를 한 개만 출력해주어야 한다.

🚩 소스코드

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

queue<int> q;
int dist[100001] = { 0 };
bool visited[100001] = { false };
int n, k;
int ans;
int memo[100001];
vector<int> path;

void bfs() {
	q.push(n);
	visited[n] = true;
	while (!q.empty()) {
		int n = q.front();
		q.pop();
		int go[3] = { n - 1, n + 1, 2 * n }; // 한 칸 앞, 한 칸 뒤, 두배 점프
		for (int i = 0; i < 3; i++) {
			int nx = go[i];
			if (0 <= nx && nx <= 100000 && !visited[nx]) {
				q.push(nx);
				visited[nx] = true;
				dist[nx] = dist[n] + 1;
				memo[nx] = n;
			}
			if (nx == k) {
				ans = dist[nx];
				return;
			}
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> k;
	if (n == k) {
		cout << '0' << '\n' << n;
	}
	else {
		bfs();
		cout << ans << '\n';
		path.push_back(k);
		for (int i = 0; i < ans; i++) {
			path.push_back(memo[k]);
			k = memo[k];
		}
		for (int i = path.size() - 1; i >= 0; i--)
			cout << path[i] << ' ';
	}
}