백준 1697 숨바꼭질

문제 링크 : https://www.acmicpc.net/problem/4354

※선행해야 할 알고리즘 : BFS, DFS

Algorithm : N에서 K까지 갈 때 count를 센다.

1. 미로찾기로 따지면 N이 시작점, K가 출구가 된다. 즉, 현재 위치값을 순간이동(*2), 오른쪽(+1), 왼쪽(-1)을 통해 바꿔가며 찾는다.

즉, 입력 예제를 통해 본다면

1   2   3  4  5 

6   7  8  9  10

11 12 13 14 15

16 17 18 19 20

빨간색은 시작점 -> 노란색은 이동거리 -> 파란색은 도착점 이 되는 것이다.

2. queue를 활용하여 BFS를 진행하면 다음과 같다.

//kuklife.tistory.com #include<iostream> #include<algorithm> #include<queue> #include<vector> using namespace std; int bfs(int n, int k) { queue<pair<int, int>> q; vector<bool> check(100001, false); q.push({ n,0 }); while (!q.empty()) { int now = q.front().first; int result = q.front().second; q.pop(); if (now < 0 || now > 100000) continue; if (check[now]) continue; check[now] = true; if (now == k) return result; q.push({ now * 2, result + 1 }); q.push({ now + 1, result + 1 }); q.push({ now - 1, result + 1 }); } } int main() { int n, k; cin >> n >> k; cout << bfs(n, k) << endl; }