13913번: 숨바꼭질 4
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
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;
}
'알고리즘 문제풀이 > DFS와 BFS' 카테고리의 다른 글
| 백준 1600 [C++] (0) | 2021.01.19 |
|---|---|
| 백준 12851 [C++] (0) | 2021.01.18 |
| 백준 19238 [C++] (0) | 2021.01.17 |
| 백준 17142 [C++] (0) | 2021.01.17 |
| 백준 16236 [C++] (0) | 2020.12.29 |
