92. 백준 1697 번 C++ 코드 및 자세한 설명

안녕하세요 코딩하는 덕구입니다.

그리디 알고리즘 문제인 BOJ 1697 번 숨바꼭질 입니다.

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

1697번: 숨바꼭질

 

백준 1439 번 C++ 정답 코드입니다. 설명은 아래에 있습니다.

#include <iostream>
#include <queue>
using namespace std;
int loc[200000] = {0,};
int N, K;

bool isValid(int x){
    if (0 <= x and x < 200000){
        if (loc[x] == 0) return true;
    }
    return false;
}

void BFS(int N){
    queue<int> Q;
    Q.push(N);
    while (!Q.empty()){
        int x = Q.front();
        Q.pop();

        if (x == K) {
            cout << loc[K];
            break;
        }

        if (isValid(x + 1)){
            Q.push(x + 1);
            loc[x + 1] = loc[x] + 1;
        }

        if (isValid(x - 1)){
            Q.push(x - 1);
            loc[x - 1] = loc[x] + 1;
        }

        if (isValid(x * 2)){
            Q.push(x * 2);
            loc[x * 2] = loc[x] + 1;
        }
    }

}
int main(){
    cin >> N >> K;
    BFS(N);

    return 0;
}

 

문제 요약

일차원 선분 안에서 수빈이가 동생을 찾는 문제입니다.

수빈이는 점 x를 기준으로 x+1 or x-1 or x*2 의 좌표로 이동가능하고, 한번 이동시마다 1초가 걸립니다.

이때 수빈이가 동생을 찾는데 걸리는 최소한의 시간을 출력하는 문제입니다.  

 

문제 접근

최단거리, 최소시간은 보통 BFS를 이용하면 문제 풀기 좋습니다.

현재 위치가 x라면 x + 1, x  - 1, x * 2 가 방문가능한지 살피고, queue에 넣습니다.

queue에 넣음과 동시에 x좌표로 이동하기까지 걸린 시간을 가져와

다음 이동시간을 계산해서 저장합니다.

x 좌표까지 이동 시간 + 1초

이를 동생을 찾을 때 까지 반복하고, 동생을 찾으면 계산한 이동시간을 출력하면 됩니다.

 

C++ 코드 구현

위의 직관을 이용하여 코드를 구현 해봅시다. BFS를 이용합니다.

 

먼저 수빈이의 위치, 동생의 위치인 N, K를 입력받고

1차원 직선을 표현하기 위해 행렬를 생성합니다.

수빈이가, 동생의 최대 위치보다 큰 범위로 이동할 수 있기 때문에 크게 잡아줬습니다. (수빈이 현재 위치 * 2로 이동 가능)

int loc[200000] = {0,};
int N, K;

cin >> N >> K;

 

어떤 좌표가 들어오면 해당 좌표가 방문 가능한지 확인해주는 함수 isVaild를 구현합니다.

좌표가 그래프 범위를 벗어나지 않는지, 이미 방문한적은 없는지 판단하는 함수입니다. 

bool isValid(int x){
    if (0 <= x and x < 200000){
        if (loc[x] == 0) return true;
    }
    return false;
}

 

BFS를 queue를 이용해 구현합니다.

좌표 x + 1, x -1, x * 2 가 방문 가능하다면, x좌표로 이동하기 까지 걸린 시간 + 1 초를 계산해 저장하고

다음번에 이동할 좌표를 queue에 넣어줍니다.

만약 방문한 좌표가 동생의 위치랑 같다면 탐색을 중지하고 걸린 시간을 출력합니다. ( if  x == K ) 

void BFS(int N){
    queue<int> Q;
    Q.push(N);
    while (!Q.empty()){
        int x = Q.front();
        Q.pop();

        if (x == K) {
            cout << loc[K];
            break;
        }

        if (isValid(x + 1)){
            Q.push(x + 1);
            loc[x + 1] = loc[x] + 1;
        }

        if (isValid(x - 1)){
            Q.push(x - 1);
            loc[x - 1] = loc[x] + 1;
        }

        if (isValid(x * 2)){
            Q.push(x * 2);
            loc[x * 2] = loc[x] + 1;
        }
    }

}

 

이제 수빈이의 위치를 시작으로 구현한 BFS 함수를 실행시키면 됩니다.

BFS(N);

 

백준 1697 번 숨바꼭질 C++ 최종 코드입니다.

#include <iostream>
#include <queue>
using namespace std;
int loc[200000] = {0,};
int N, K;

bool isValid(int x){
    if (0 <= x and x < 200000){
        if (loc[x] == 0) return true;
    }
    return false;
}

void BFS(int N){
    queue<int> Q;
    Q.push(N);
    while (!Q.empty()){
        int x = Q.front();
        Q.pop();

        if (x == K) {
            cout << loc[K];
            break;
        }

        if (isValid(x + 1)){
            Q.push(x + 1);
            loc[x + 1] = loc[x] + 1;
        }

        if (isValid(x - 1)){
            Q.push(x - 1);
            loc[x - 1] = loc[x] + 1;
        }

        if (isValid(x * 2)){
            Q.push(x * 2);
            loc[x * 2] = loc[x] + 1;
        }
    }

}
int main(){
    cin >> N >> K;
    BFS(N);

    return 0;
}

 

제가 운영하는 오픈 카톡방입니다. 알고리즘, 코딩, 취업정보 등 자유롭게 질문, 답변 및 대화 나눠요.

https://open.kakao.com/o/guGhqGAg

알고리즘, 코딩, 개발자 취업 질문방 (비번 4321)

 

백준 1697 번 숨바꼭질 자세한 설명 및 C++ 코드였습니다.

감사합니다.