M'S Blog

M'S Blog

WWDC20 student challenge Winner!

백준 1697 - 숨바꼭질

최대 1 분 소요

문제

백준 1697 - 숨바꼭질 풀러가기

문제 분석

동생과 수빈이의 위치를 정점 이라 생각 할 수 있고, 수빈이가 이동하는데 각각 1초 가 걸리므로 가중치가 1 이라고 생각 할 수 있다.

이때, 동생을 찾는 가장 빠른 시간을 구하는 문제이고

따라서 bfs 를 이용하여 문제를 풀면 된다.

그렇다면 자료구조는 뭘 이용해야 할까?

이용하지 않아도 된다. 왜냐하면 현재 위치에서 x-1, x+1, x*2 만 확인해주면 되기 때문이다.

문제 풀이(C++)

  1. 전체 코드

    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
    #include <cstdio>
    #include <queue>
     
    using namespace std;
     
    bool visit[100001];
    int time[100001];
     
    queue<int> q;
     
    int n, k;
     
    void bfs() {
        while (!q.empty()) {
            int now = q.front();
     
            if (now == k) {
                break;
            }
     
            if (now - 1 >= 0) {
                if (!visit[now - 1]) {
                    q.push(now - 1);
                    visit[now - 1] = true;
                    time[now - 1] = time[now] + 1;
                }
            }
     
            if (now + 1 <= 100000) {
                if (!visit[now + 1]) {
                    visit[now + 1] = true;
                    q.push(now + 1);
                    time[now + 1] = time[now] + 1;
                }
            }
     
            if (now * 2 <= 100000) {
                if (!visit[now * 2]) {
                    visit[now *2] = true;
                    q.push(now * 2);
                    time[now * 2] = time[now] + 1;
                }
            }
            q.pop();
        }
    }
     
    int main() {
        
        scanf("%d %d", &n, &k);
     
        q.push(n);
     
        bfs();
     
        printf("%d", time[k]);
     
        return 0;
    }
    		cs





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

댓글남기기

참고