반응형

https://www.acmicpc.net/problem/13913

 

13913번: 숨바꼭질 4

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. N이 K보다 클 경우 x - 1로 이동할 수밖에 없으므로 N부터 K까지 1씩 빼주면서 출력합니다.

 

2. 아닐 경우 bfs를 이용하여 이동하고, 어디로 부터 왔는지 from 배열에 저장합니다.

 

3. cur == K일 경우 from 배열을 체크하면서 어디서부터 왔는지 ans vector에 저장합니다.

 

4. 역순으로 출력합니다.

 

[ 소스코드 ]

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
int N, K;
bool visited[200001];
int from[200001];
 
int main()
{
    scanf("%d %d", &N, &K);
 
    if (N > K) {    //N이 K보다 크다면 x-1로 밖에 이동할 수 없으므로
        printf("%d\n", N - K);
        for (int i = N; i >= K; i--) {
            printf("%d ", i);
        }
        return 0;
    }
 
    visited[N] = true;
 
    queue<int> q;
 
    q.push({ N });
 
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        if (cur == K) {
            vector<int> ans;    //이동 경로
            for (int i = K; i != N; i=from[i]) {
                ans.push_back(i);
            }
            printf("%d\n", ans.size());
            printf("%d ", N);
            for (int i = ans.size() - 1; i >= 0; i--) {
                printf("%d ", ans[i]);
            }
        }
 
        if (cur - 1 >= 0) {
            if (visited[cur - 1] != true) {
                visited[cur - 1] = true;
                from[cur - 1] = cur;    //어디로 부터 왔는지 이동한 위치에서 저장
                q.push(cur - 1);
            }
        }
        if (visited[cur + 1] != true && cur < K) {
            visited[cur + 1] = true;
            from[cur + 1] = cur;
            q.push(cur + 1);
        }
        if (cur <= K) {
            if (visited[cur * 2] != true) {
                visited[cur * 2] = true;
                from[cur * 2] = cur;
                q.push(cur * 2);
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 15681번 - 트리와 쿼리 (C++)  (0) 2022.11.14
[ 백준 ] 7682번 - 틱택토 (C++)  (0) 2022.11.13
[ 백준 ] 1976번 - 여행 가자 (C++)  (0) 2022.11.11
[ 백준 ] 12286번 - 돌 그룹 (C++)  (0) 2022.11.10
[ 백준 ] 2281번 - 데스노트 (C++)  (0) 2022.11.09

+ Recent posts

티스토리툴바