[백준] 13913 숨바꼭질 4⭐

[백준] 13913 숨바꼭질 4

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

틀린 풀이

• 시간초과

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>

using namespace std;

void getMinMove(int start, int end) {

	//<-curMove, 이동 경로>
	priority_queue<pair<int, string>> q;
	q.push({ 0, to_string(start)});

	int visited[100001] = { 0 };

	while (!q.empty()) {
		int curMove = -q.top().first;
		string curPath = q.top().second;
		q.pop();

		int curX;
		string curXStr = "";
		for (int i = curPath.length() - 1; i >= 0; --i) {
			if (curPath[i] == ' ') {
				break;
			}
			curXStr += curPath[i];
		}
		reverse(curXStr.begin(), curXStr.end());
		curX = stoi(curXStr);

		if (curX == end) {
			cout << curMove << "\n" << curPath;
			return;
		}

		if (visited[curX]) continue;
		visited[curX] = 1;

		if ((curX - 1 >= 0) && (!visited[curX - 1])) {
			q.push({ -(curMove + 1), curPath + " " + to_string(curX-1)});
		}

		if ((curX + 1 <= 100000) && (!visited[curX + 1])) {
			q.push({ -(curMove + 1),  curPath + " " + to_string(curX + 1) });
		}

		if ((curX * 2 <= 100000) && (!visited[curX * 2])) {
			q.push({ -(curMove + 1), curPath + " " + to_string(curX *2) });
		}
	}
}

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

	int N, K;
	cin >> N >> K;
	
	getMinMove(N, K);
	return 0;
}

풀이

• bfs 과정에서 priority_queue에 지금까지 방문한 모든 좌표를 저장하는 것이 아닌, 직전에 방문한 좌표만 저장
  -> prevVisited[현재 좌표] = 직전에 방문한 좌표
  -> bfs 종료 후 prevVisited 순회하며 경로 만들어 출력

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>

using namespace std;


void getMinMove(int start, int end) {

	//<-curMove, <curX, prevX>>
	priority_queue<pair<int, pair<int, int>>> q;
	q.push({ 0, {start, -1} });

	int visited[100001] = { 0 };
	int prevVisited[100001] = { 0 };

	while (!q.empty()) {
		int curMove = -q.top().first;
		int curX = q.top().second.first;
		int prevX = q.top().second.second;
		q.pop();
		

		if (visited[curX]) continue;
		visited[curX] = 1;
		prevVisited[curX] = prevX;
	
		if (curX == end) {
			cout << curMove << "\n";
			break;
		}


		if ((curX - 1 >= 0) && (!visited[curX - 1])) {
			q.push({ -(curMove + 1), {curX - 1, curX} });
		}

		if ((curX + 1 <= 100000) && (!visited[curX + 1])) {
			q.push({ -(curMove + 1), {curX + 1, curX} });
		}

		if ((curX * 2 <= 100000) && (!visited[curX * 2])) {
			q.push({ -(curMove + 1), {curX*2,  curX} });
		}
	}
	
	int cur = end;
	vector<int> path;
	while (cur != -1) {
		path.push_back(cur);
		cur = prevVisited[cur];
	}
	reverse(path.begin(), path.end());

	for (int i = 0; i < path.size(); ++i) {
		cout << path[i] << " ";
	}
	return;
}

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

	int N, K;
	cin >> N >> K;

	getMinMove(N, K);
	return 0;
}

📌참고자료

• [백준] 1697 숨바꼭질
  https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-1697-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88