13913번: 숨바꼭질 4
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
[난이도] Gold4
[유형] BFS
[풀이]
최단 경로까지 출력해야 하므로 방문 체크를 할때 어디서 왔는지를 저장 후 답을 찾았을 때 재귀적으로 출력한다.
#include <cstdio> #include <queue> #include <cstring> using namespace std; int s,e,visit[100001]; void prt(int n){ if(n==-2) return; prt(visit[n]); printf("%d ",n); } int main(){ scanf("%d%d",&s,&e); memset(visit,-1,sizeof(visit)); queue<int> q; visit[s] = -2; q.push(s); int cnt = 0; while(!q.empty()){ int qsz = q.size(); while(qsz--){ int cur = q.front(); q.pop(); if(cur==e){ printf("%d\n",cnt); prt(cur); return 0; } int nxt; if(cur+1<=100000) { nxt = cur+1; if(visit[nxt]==-1){ visit[nxt]=cur; q.push(nxt); } } if(cur-1>=0) { nxt = cur-1; if(visit[nxt]==-1){ visit[nxt]=cur; q.push(nxt); } } if(cur*2<=100000) { nxt = cur*2; if(visit[nxt]==-1){ visit[nxt]=cur; q.push(nxt); } } } cnt++; } }
github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/13913.cpp
'Problem-Solving > BOJ' 카테고리의 다른 글
| [BOJ/백준][Gold4] 15685 : 드래곤 커브 (C++) (0) | 2020.12.13 |
|---|---|
| [BOJ/백준][Gold4] 14002 : 가장 긴 증가하는 부분수열 4 (C++) (0) | 2020.12.13 |
| [BOJ/백준][Gold4] 1351 : 무한 수열 (C++) (0) | 2020.12.13 |
| [BOJ/백준][Gold4] 1339 : 단어 수학 (C++) (0) | 2020.12.13 |
| [BOJ/백준][Gold4] 1199 : 오일러 회로(C++) (0) | 2020.12.12 |