백준 13913 숨바꼭질4

www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

1697 숨바꼭질 문제에 경로 출력이 포함된 문제.

 

초반에 구현한 코드는 아래와 같다. 큐 q에 새로운 원소를 넣을 때 경로를 포함한 temp2큐를 함께 넣어주었다.

#include<iostream>
#include<queue>
using namespace std;
int n, k;
int visited[200001];

int main() {
	cin >> n >> k;
	if (n == k) {
		cout << 0 << "\n" << k;
		return 0;
	}
	else if (n * 2 == k) {
		cout << 1 << "\n" << n << " " << k;
		return 0;
	}
	else if (n > k) {
		cout << n - k << "\n";
		int j = n;
		for (int i = 0; i <= (n - k); i++) {
			cout << j-- << " ";
		}
		return 0;
	}
	queue<pair<int, queue<int>>> q;
	queue<int> temp;
	temp.push(n);
	q.push({ n, temp });
	visited[n] = 1;
	while (!q.empty()) {
		int cur = q.front().first;
		temp = q.front().second;
		q.pop();
		if ((cur + 1) == k || (cur - 1) == k || (cur * 2) == k) {
			cout << visited[cur] << endl;
			for (int i = 0; i < visited[cur]; i++) {
				cout << temp.front() << " ";
				temp.pop();
			}
			cout << k;
			return 0;
		}
		if (cur < k && visited[cur + 1] == 0) {
			queue<int> temp2 = temp;
			temp2.push(cur + 1);
			q.push({ cur + 1, temp2 });
			visited[cur + 1] = visited[cur] + 1;
		}
		if (cur > 0 && visited[cur - 1] == 0) {
			queue<int> temp2 = temp;
			temp2.push(cur - 1);
			q.push({ cur - 1, temp2 });
			visited[cur - 1] = visited[cur] + 1;
		}
		if (cur < k && visited[cur * 2] == 0) {
			queue<int> temp2 = temp;
			temp2.push(cur * 2);
			q.push({ cur * 2, temp2 });
			visited[cur * 2] = visited[cur] + 1;
		}
	}
	return 0;
}

답은 맞았지만, else if (n>k)~ 코드를 넣기 전까진 시간초과가 떴다.
큐를 매번 가지고 다니면서 temp2에 복사했다가 다시 넣고 하는 과정이 너무 부담이 크다.

메모리 / 시간

 

 

이를 개선하기 위해 새로 짠 코드는 아래와 같다.
vector를 하나 더 만들어서 바로 전 값을 현재 위치를 인덱스로 하는 공간에 저장한다.
ex) 5->10->9->18->17이면, 10에 들어갈 때 v[10]=5, 9에 들어갈 때 v[9]=10,.. 그러면 마지막 v[17]=18이므로, 출력할 때 17에서 시작해서 값을 출력하고, 18로 들어가서 v[18]값을 출력하고, v[9]에서 10을 출력하고,.. 반복하면 된다.
여기선 거꾸로 출력되기 때문에 출력값을 다시 stack에 저장해서 원래 순서대로 출력한다. 아예 n이 아닌 k에서 시작해서 한번에 바른 순서대로 출력하는 방법도 있다.

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int n, k;
int visited[200001];
vector<int> v(200001);
vector<int> stack;

int main() {
	cin >> n >> k;
	if (n == k) {
		cout << 0 << "\n" << k;
		return 0;
	}
	else if (n * 2 == k) {
		cout << 1 << "\n" << n << " " << k;
		return 0;
	}
	else if (n > k) {
		cout << n - k << "\n";
		int j = n;
		for (int i = 0; i <= (n - k); i++) {
			cout << j-- << " ";
		}
		return 0;
	}
	queue<int> q;
	q.push(n);
	visited[n] = 1;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		if (cur == k) {
			cout << visited[cur] - 1 << "\n"; // visited[n]=1로 시작하므로 1 뺌
			int temp = v[k];
			cout << n << " ";
			while (temp != n) {
				stack.push_back(temp);
				temp = v[temp];
			}
			while (!stack.empty()) {
				cout << stack.back() << " ";
				stack.pop_back();
			}
			cout << k;
			return 0;
		}
		if (cur < k && cur * 2 <= 200000 && visited[cur * 2] == 0) {
			q.push(cur * 2);
			visited[cur * 2] = visited[cur] + 1;
			v[cur * 2] = cur;
		}
		if (cur < k && visited[cur + 1] == 0) {
			q.push(cur + 1);
			visited[cur + 1] = visited[cur] + 1;
			v[cur + 1] = cur;
		}
		if (cur > 0 && visited[cur - 1] == 0) {
			q.push(cur - 1);
			visited[cur - 1] = visited[cur] + 1;
			v[cur - 1] = cur;
		}
	}
	return 0;
}

 이전에 38번째 줄에서 while(temp!=n){..} 대신 while(temp!=0)으로 뒀었는데, 예제 5 17이나 내가 직접 입력한 값 모두 올바르게 나왔지만 답은 틀려서 오랫동안 헤맸다. 문제는 아래와 같은 케이스에서 발생했다.

 0 1을 입력하면 1  /  0 1이 출력돼야 하는데, 1만 출력됐다. while(temp!=0)으로 두었기에 v[1]=0을 유효한 값으로 인식하지 않고 while문을 빠져나온 것이다.

 while(temp!=n)으로 고치고 그 위에 n값을 따로 출력하도록 했더니 위와 같이 바르게 나오고 제출 결과도 정답이었다.

메모리 / 시간

 메모리와 시간도 크게 줄었다.

 

 

 

꿀팁)

 [질문 검색] 페이지에서 다른 사람들이 질문한 글들을 보면 댓글에 이것도 한번 시도해 보라며 케이스를 제시하는 사람들이 많은데, 전부 대입해보면 내 코드의 어느 부분이 틀렸는지 알게 될 수도 있다.