M'S Blog

M'S Blog

WWDC20 student challenge Winner!

백준 13549 - 숨바꼭질3

최대 1 분 소요

문제

백준 13549 - 숨바꼭질3 풀러가기

문제 분석

이 문제의 경우에는 모든 연산이 1초 가 아니다.

bfs는 모든 가중치가 1인 경우에 적용할 수 있다고 생각하여 bfs로 풀 수 없다고 생각 할 수 있는데, 그렇지 않다.

큐를 2개 이용하거나, 덱을 이용하면 bfs로 풀 수 있다.

문제 풀이(C++)

  1. 전체 코드(큐 2개)

    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
    #include <cstdio>
    #include <queue>
    #include <cstring>
     
    using namespace std;
     
    int cnt[100001];
     
    queue<int> q1;
    queue<int> q2;
     
    void bfs() {
        while (!q1.empty()) {
            int c = q1.front();
     
            if (c * 2 <= 100000 && cnt[c * 2] == -1) {
                cnt[c * 2] = cnt[c];
                q1.push(c * 2);
            }
     
            if (c - 1 >= 0 && cnt[c - 1] == -1) {
                cnt[c - 1] = cnt[c] + 1;
                q2.push(c - 1);
            }
     
            if (c + 1 <= 100000 && cnt[c+ 1] == -1) {
                cnt[c + 1] = cnt[c] + 1;
                q2.push(c + 1);
            }
     
            q1.pop();
        }
    }
     
    int main() {
        int n, k;
     
        scanf("%d %d", &n, &k);
     
        memset(cnt, -1, sizeof(cnt));
     
        cnt[n] = 0;
        q1.push(n);
     
        while (cnt[k] == -1) {
            bfs();
            q1 = q2;
            q2 = queue<int>();
        }
     
        printf("%d", cnt[k]);
     
        return 0;
    }
    		cs

  2. 전체 코드(덱 사용)

    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
    #include <cstdio>
    #include <cstring>
    #include <deque>
     
    using namespace std;
     
    int cnt[100001];
     
    deque<int> d;
     
    void bfs() {
        while (!d.empty()) {
            int c = d.front();
            d.pop_front();
     
            if (c * 2 <= 100000 && cnt[c * 2] == -1) {
                cnt[c * 2] = cnt[c];
                d.push_front(c*2);
            }
     
            if (c - 1 >= 0 && cnt[c - 1] == -1) {
                cnt[c - 1] = cnt[c] + 1;
                d.push_back(c - 1);
            }
     
            if (c + 1 <= 100000 && cnt[c + 1] == -1) {
                cnt[c + 1] = cnt[c] + 1;
                d.push_back(c + 1);
            }
        }
    }
     
    int main() {
        int n, k;
     
        scanf("%d %d", &n, &k);
     
        memset(cnt, -1, sizeof(cnt));
     
        cnt[n] = 0;
        d.push_back(n);
     
        bfs();
     
        printf("%d", cnt[k]);
     
        return 0;
    }
    		cs

연관 문제

  • 백준 1261 - 알고스팟






    아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

</html>

댓글남기기

참고