728x90
반응형
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#include<stdio.h>
#include<queue>
#include<string.h>
#include<iostream>
#include<map>
using namespace std;
int N, K;
//map<long long, int>chk;
int chk[100004];
void init() {
cin >> N >> K;
memset(chk, 0x7f, sizeof(chk));
}
struct Data {
int pos, cnt;
};
int Min = 0x7fffffff;
void hindPlay() {
queue<Data>q;
q.push({ N,0 });
chk[N] = 1;
while (!q.empty()) {
Data c = q.front(); q.pop();
if (c.pos == K) {
if (Min > c.cnt)Min = c.cnt;
}
if (chk[c.pos - 1] >c.cnt+1 && 0 <= c.pos - 1 && c.pos - 1 <= 100000) {
chk[c.pos - 1] = c.cnt+1;
q.push({ c.pos - 1,c.cnt + 1 });
}
if (chk[c.pos + 1] >c.cnt+1&& 0 <= c.pos + 1 && c.pos + 1 <= 100000) {
chk[c.pos + 1] = c.cnt+1;
q.push({ c.pos + 1,c.cnt + 1 });
}
if (chk[c.pos * 2] >c.cnt&& 0 <= c.pos * 2 && c.pos * 2 <= 100000) {
chk[c.pos * 2] = c.cnt;
q.push({ c.pos * 2,c.cnt });
}
}
}
int main(void) {
init();
hindPlay();
cout << Min << endl;
return 0;
}
|
이문제는 가장 주의를 해야하는게 그위치를 찾자마자 나오게하면 문제가 생길 수있다. 그러므로
다엑스트라 기법 비슷한 방법을 이용해야합니다. 체크를 하지만 체크했던것보다 작은 경로였으면 다시 그위치에서
큐를 돌려줌으로써 더 최소의 방법으로 가는것이죠. 그래서 최소를 뽑으면서 큐가 전부끝나야 합니다.
비교적 쉬운 문제 이므로 소스를 보시면 이해가 되실겁니다.
오늘은 여기까지이고 여러분들도 파이팅
728x90
반응형
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 3568 iSharp (0) | 2019.10.04 |
|---|---|
| 백준 14226 이모티콘 (0) | 2019.10.03 |
| 백준 2065 나룻배 (0) | 2019.10.02 |
| 백준 2931 가스관 (0) | 2019.10.02 |
| 백준 16137 견우와 직녀 (0) | 2019.09.30 |
댓글