Machineboy空
13913 숨바꼭질 4 : bfs 본문
https://www.acmicpc.net/problem/13913
문제요약
1칸 좌우 이동, 2배 이동이 가능할 때, 도착점으로 가는 최단 시간과 궤적 나타내기
난이도
Gold 4
풀이 포인트
- prev에 계속 쌓아두며 역추적해가는 방법
- for문 사용법
for (int next : {now - 1, now + 1, now * 2})
REVIEW
우선 너무 오랜만에 풀어서 using namespace std 구문도 낯설어질 뻔 했다.
bfs의 기본 용법을 따르되 for문으로 재귀 스럽게 +1, -1, *2를 구현하는 방법과,
prev에 전 위치를 기록해 두고, 거슬러가며 for문을 돌리는 방법 등을 잘 익혀야 한다.
CODE
#include <bits/stdc++.h>
using namespace std;
// 경로 추적은 prev
#define prev aaa
#define next aaaa
const int max_n = 200004;
int visited[max_n], prev[max_n], ret,here, cnt, next;
int n, k;
vector<int> v;
queue<int> q;
int main(){
cin >> n >> k;
visited[n] = 1;
q.push(n);
while(q.size()){
here = q.front();
//cout << "현재 here는 " << here <<'\n';
q.pop();
if(here == k){
//cout << "도착지에 도달했다"<<'\n';
ret = visited[k];
break;
}
for(int next: {here + 1, here - 1, here * 2}){
if(next >= max_n || next < 0 || visited[next]) continue;
//cout << "현재 next는 "<< next <<" 처음 방문했다."<<'\n';
visited[next] = visited[here] + 1;
//다음을 넣으면 그 전의 발자취가 나오는!
prev[next] = here;
q.push(next);
}
}
// 거슬러 올라감.
for(int i = k; i != n; i = prev[i]){
// cout << "현재 i는 " << i << '\n';
v.push_back(i);
}
v.push_back(n);
cout << ret -1 << '\n';
reverse(v.begin(), v.end());
for(int i : v) cout << i << ' ';
return 0;
}
'Computer > Coding Test' 카테고리의 다른 글
1189: 컴백홈 - DFS (0) | 2024.03.22 |
---|---|
17071: 숨바꼭질 5 (0) | 2024.03.20 |
12851 : 숨바꼭질 2 - BFS (1) | 2024.02.29 |
15537 : 괄호 추가하기 - 재귀 (1) | 2024.02.28 |
12869 : 뮤탈리스크 - BFS, DP (1) | 2024.02.27 |