백준 13913 [C++]

www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

 

 

1. 풀이방법

 

- 걸리는 시간만 출력하라 했으면 정말 쉬웠을 텐데, 어떤식으로 경로도 출력 해야 합니다.

 

- 처음에는 출발점 1, 여기서 분화되는것이 3개 ( 배열:  0 | 1 2 3 )

 

- 그 다음 단계에서는 index 1,2,3 의 값(출발점에서 각각 3 개씩) ( 배열: 0 | 1 2 3 | 4 5 6 7 8 9 10 11 12 )

 

- 이런식으로 3의 제곱수로 분화된다는 것을 착안하여 k를 처음 발견한 위치의 index를 계산을 통해 앞쪽으로 이동

 

- 하면서 출력하였는데 시간이 너무 오래 걸립니다. (특히나 모든 경우의 수를 다 분화해서 가야하므로)

 

- 그래서 index계산을 통해서 가는 것을 포기하고 새로 bfs를 돌때 visit을 통해 방문한 지점은 다시 가지 않으므로

 

- 트리와 같은 느낌으로 어디서 왔는지 (부모가 누군지) 를 배열하나를 선언해서 넣어주면서 bfs를 돌고

 

- 나중에 k에서 시작해서 ---> 어디서왔는지를 쭉 탐색 ---> n을 발견하면 멈춤 이런식으로 구현하였습니다.

 

 

 

 

2. 주의사항

 

- 저 같은경우 출발점과 도착점은 무조건 출력해야 하는줄 알아서 

 

- 입력이 5 5 로 같으면 출력이 0 (시간) 5 5 (경로) 이렇게 인 것으로 착각 했으나

 

- n의 이동 경로이므로 5 하나만 출력해야 했습니다.

 

 

 

 

3. 나의코드

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;

int n, k;
queue<int> tmpq;
bool visit[100001];
int from[100001]; //어디서 온 놈인지르 표시해주자
vector<int> resultarr;

int second = 0;

int bfs() {
	while (1) {
		int qsize = tmpq.size();
		while (qsize--) {
			int nextn = tmpq.front();
			tmpq.pop();
			if (nextn == k) { return second; }
			//1증가
			if (nextn + 1 <= 100000&& visit[nextn + 1] == false) {
				resultarr.push_back(2 * nextn);
				tmpq.push(nextn+1);
				visit[nextn + 1] = true;
				from[nextn + 1] = nextn;
			}

			if (nextn - 1 >= 0 && visit[nextn - 1] == false ) {
				tmpq.push(nextn - 1);
				resultarr.push_back(nextn - 1);
				visit[nextn - 1] = true;
				from[nextn - 1] = nextn;
			}
			
			if (nextn * 2 <= 100000&& visit[2 * nextn] == false) {
				tmpq.push(nextn *2);
				resultarr.push_back(nextn *2);
				visit[2 * nextn] = true;
				from[2 * nextn]=nextn;
			}
		}
		second++;
	}
}
void findparent() {
	int tmpk = k;
	resultarr.clear();
	resultarr.push_back(tmpk);
	while (1) {
		if (from[tmpk] == n) { resultarr.push_back(n); break; }
		resultarr.push_back(from[tmpk]);
		tmpk = from[tmpk];
	}
	for (int i = resultarr.size() - 1; i >= 0; i--) {
		cout<<resultarr[i] << " ";
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> k;
	int second = 0;
	if (n == k) { cout << 0 << "\n"; cout << n; return 0; }
	if (n > k) {
		cout << n-k<<"\n";
		cout << n << " ";
		for (int i = 1; i < (n - k); i++) {
			cout << n - i << " ";
		}
		cout << k << " ";
	}
	else {
		tmpq.push(n);
		visit[n] = true;
		cout << bfs() << "\n";
		findparent();
	}
	return 0;
}