-
백준 12851번 숨바꼭질2PS 2020. 3. 10. 18:55
https://www.acmicpc.net/problem/12851
<접근방법>
탐색 문제입니다.
1에서 2까지 도달한다고 합시다.
+1, *2 이렇게 두 가지 방법이 있습니다.
즉, 탐색을 해가며 그 지점에 도달한 횟수도 저장해야 합니다.
그런데 문제가 있습니다.
1 -> 2 -> 3 -> 2 는 최단 방법이 아니므로 횟수를 저장할 때 걸러야 합니다.
즉, 이것에 대한 처리도 해야 합니다.
참고로..
가중치를 거쳐간 숫자의 갯수라고 합시다.
코드상으로 무조건 가중치가 낮은 순으로 탐색이 됩니다.
그러니까 먼저 도달한 방법이 최단코스 입니다.
<느낀 점>
<코드>
#include <iostream> #include <algorithm> #include <queue> using namespace std; int n, k; int visit[100001]; int dist[100001]; queue<int> q; void bfs() { int res = 0, flag = 0; q.push(n); while (!flag) { int sz = q.size(); while (sz--) { int x = q.front(); q.pop(); if (x == k) { flag++; } for (int nx : {x - 1, x + 1, x * 2}) { if (0 <= nx && nx <= 100000) { if (!dist[nx] || dist[nx] == dist[x] + 1) { q.push(nx); dist[nx] = dist[x] + 1; } } } } res++; } cout << res-1 << '\n'; cout << flag << '\n'; } int main() { cin >> n >> k; bfs(); return 0; }
#include <iostream> #include <algorithm> #include <queue> using namespace std; int n, k; bool visit[100001]; queue<int> q; void bfs() { int res = 0, flag = 0; q.push(n); while (!flag) { int sz = q.size(); while (sz--) { int x = q.front(); q.pop(); visit[x] = true; if (x == k) { flag++; } for (int nx : {x - 1, x + 1, x * 2}) { if (0 <= nx && nx <= 100000) { if (!visit[nx]) { q.push(nx); } } } } res++; } cout << res - 1 << '\n'; cout << flag << '\n'; } int main() { cin >> n >> k; bfs(); return 0; }
'PS' 카테고리의 다른 글
백준 13913번 숨바꼭질4 (0) 2020.03.10 백준 13549번 숨바꼭질 3 (0) 2020.03.10 백준 1697번 숨바꼭질 (0) 2020.03.10 백준 17825번 주사위 윷놀이 (0) 2020.03.09 백준 16932번 모양 만들기 (1) 2020.03.07