#13913. 숨바꼭질 4

Problem

• 문제링크

Solution

• BFS 탐색을 하되, 경로를 알고 있어야 하기에 path[to] = from 을 사용한다.
• 즉, 5→6→8→10 이라면 path[10]에는 8, path[8]에는 6이 저장되어 있다.

• 경로를 출력하기 위해 재귀함수를 사용한다.

  (5, 10) 4. 출력
  	(5, 8) 3. 출력
  		(5, 6)  2. 출력
  			(5, 5) 1. 출력

  1 Try

• code

  #include <iostream>
  #include <queue>
  #include <vector>
  #define MAX 100000
  using namespace std;
  int N, K;
  bool end_flag;
  int dist[MAX+1];
  vector<int> path;
  int dx[4] = { -1, 1, 0, 0 };
  int dy[4] = { 0, 0, -1, 1 };
  void Input() {
  	cin >> N >> K;
  }
  void PrintPath() {
  	for (auto e : path) cout << e << " ";
  	cout << "\n";
  }
  void BFS() {
  	queue<int> q;
  	q.push(N);
  	while (!q.empty()) {
  		int n = q.front();
  		q.pop();
  		if (n == K) return;
  		if (n > 0 && dist[n - 1] == 0) {
  			dist[n - 1] = dist[n] + 1;
  			q.push(n - 1);
  		}
  		if (n < MAX && dist[n + 1] == 0) {
  			dist[n + 1] = dist[n] + 1;
  			q.push(n + 1);
  		}
  		if (2 * n <= MAX && dist[2 * n] == 0) {
  			dist[2 * n] = dist[n] + 1;
  			q.push(2 * n);
  		}
  	}
  }
  void DFS(int n, int cnt) {
  	if (end_flag == true) return;
  	if (dist[K] == cnt && n == K) {
  		cout << dist[K] << "\n";
  		PrintPath();
  		end_flag = true;
  		return;
  	}
  	if (dist[K] == cnt) return;
  	if (n > 0) {
  		path.push_back(n - 1);
  		DFS(n - 1, cnt + 1);
  		path.pop_back();
  	}
  	if (n < MAX) {
  		path.push_back(n +1);
  		DFS(n + 1, cnt + 1);
  		path.pop_back();
  	}
  	if (2 * n <= MAX) {
  		path.push_back(2 * n);
  		DFS(2 * n, cnt + 1);
  		path.pop_back();
  	}
  }
  void Solve() {
  	BFS();
  	path.push_back(N);
  	DFS(N, 0);
  }
  int main() {
  	Input();
  	Solve();
  	return 0;
  }

  BFS + DFS로 구하니 시간초과 (BFS로 depth를 구하고 그 depth만큼 DFS를 수행하도록 하였다.)

2 Try

#include <iostream>
#include <queue>
#include <vector>
#define MAX 100000
using namespace std;
int N, K;
int dist[MAX + 1];
int path[MAX + 1];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
void Input() {
	cin >> N >> K;
}
void PrintPath(int from, int to) {
	if (from != to) {
		PrintPath(from, path[to]);
	}
	cout << to << " ";
}
void BFS() {
	queue<int> q;
	q.push(N);
	while (!q.empty()) {
		int n = q.front();
		q.pop();
		if (n == K) return;
		if (n > 0 && dist[n - 1] == 0) {
			dist[n - 1] = dist[n] + 1;
			path[n - 1] = n;
			q.push(n - 1);
		}
		if (n < MAX && dist[n + 1] == 0) {
			dist[n + 1] = dist[n] + 1;
			path[n + 1] = n;
			q.push(n + 1);
		}
		if (2 * n <= MAX && dist[2 * n] == 0) {
			dist[2 * n] = dist[n] + 1;
			path[2 * n] = n;
			q.push(2 * n);
		}
	}
}
void Solve() {
	BFS();
	cout << dist[K] << "\n";
	PrintPath(N, K);
}
int main() {
	Input();
	Solve();
	return 0;
}