알고리즘/acmicpc
[백준][13549번] 숨바꼭질 3[cpp, c++]
장그래
2020. 2. 1. 00:49
반응형
백준 13549 숨바꼭질3
- bfs 문제이다.
- 기존 숨바꼭질과 로직이 살짝 다르다.
- https://www.acmicpc.net/problem/13549
13549번: 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는
www.acmicpc.net
- 풀이방법
1) 순간이동의 시간은 0초니깐 순간이동 먼저 큐에 넣어준다.
2) 배열의 범위와 MAX값을 잘 설정한다.
3) MAX값이 2배가 됐을 때 배열에 담길 수 있는 크기여야한다.
#include<iostream>
#include<queue>
using namespace std;
queue<pair <int, int>> q;
bool check[2000000];
int N, K;
void bfs() {
while (!q.empty()) {
int x = q.front().first;
int time = q.front().second;
check[x] = true;
q.pop();
if (x == K) { //도착
cout << time << "\n";
break;
}
//순간이동
int x3 = 2 * x;
if (x3 >= 0 && x3 <= 200000 && check[x3] == false) {
q.push(make_pair(x3, time));
check[x3] = true;
}
// -1
int x1 = x - 1;
if (x1 >= 0 && x1 <= 200000 && check[x1] == false) {
q.push(make_pair(x1, time + 1));
check[x1] = true;
}
// +1
int x2 = x + 1;
if (x2 >= 0 && x2 <= 200000 && check[x2] == false) {
q.push(make_pair(x2, time + 1));
check[x2] = true;
}
}
}
int main(void) {
cin >> N >> K;
q.push(make_pair(N, 0));
bfs();
return 0;
}
반응형