728x90
반응형
12851번: 숨바꼭질 2
문제
https://www.acmicpc.net/problem/12851
풀이
BFS로 풀었다. 큐에는 pair로 좌표와 걸린 시간을 넣어줬다. 처음으로 K위치에 도달한 경우, m을 걸린 시간으로 할당하고 cnt++ 해준다. BFS 특성상 이후 다시 K에 도달하는 경우는 반드시 걸린 시간이 같거나 길 수밖에 없다. 따라서 K에 도달할 때마다 cnt++ 해주고 처음으로 더 긴 시간이 되면 BFS를 탈출한다.
코드
#include <bits/stdc++.h>
using namespace std;
int n, k, cnt = 0, m = 2147483647;
vector<int> visited(100001, 0);
void bfs(int xx) {
queue<pair<int, int>> q;
q.push({xx, 0});
visited[xx] = 1;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
visited[x] = 1;
q.pop();
if (m < y)
break;
if (x == k) {
m = y;
cnt++;
}
if (x + 1 >= 0 && x + 1 <= 100000)
if (!visited[x + 1])
q.push({x + 1, y + 1});
if (x - 1 >= 0 && x - 1 <= 100000)
if (!visited[x - 1])
q.push({x - 1, y + 1});
if (x * 2 >= 0 && x * 2 <= 100000)
if (!visited[x * 2])
q.push({x * 2, y + 1});
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> n >> k;
bfs(n);
cout << m << '\n'
<< cnt;
return 0;
}
728x90
반응형
'Problem Solving > BOJ' 카테고리의 다른 글
[백준 / BOJ] C++ 11054 가장 긴 바이토닉 부분 수열 (0) | 2023.02.23 |
---|---|
[백준 / BOJ] C++ 13549 숨바꼭질 3 (0) | 2023.02.23 |
[백준 / BOJ] C++ 1697 숨바꼭질 (0) | 2023.02.23 |
[백준 / BOJ] C++ 1865 웜홀 (0) | 2023.02.22 |
[백준 / BOJ] C++ 11657 타임머신 (0) | 2023.02.22 |