[BaekJoon 1697번] 숨바꼭질(C++)

※주의※
저의 풀이가 정답은 아닙니다.
다른 코드가 더 효율적이거나 좋을 수 있습니다.
언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

[문제 풀이 사이트]

 

1697번: 숨바꼭질

 

[문제 설명]

 

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

[입력]

 

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

[입출력 예]

 

5 17

 

[힌트]

 

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

[문제 풀이]

 

2차원 배열 BFS 문제만 풀다가 1차원으로 넘어와서 푸니까 쉽게 풀렸다.

수빈이의 위치에서 1초 후에 갈 수 있는 모든 좌표를 큐에 넣고 BFS로 탐색하는 방향으로 잡았다.
그리고 가장 빠른 시간을 출력해야하므로 이미 방문했던 좌표는 중복해서 가지 않도록 했다.

추가적으로 해당 위치에 도달했을 때 걸린 시간을 넣어주기 위한 배열을 만들었다.
예를 들면 배열[5] = 0초, 배열[4] = 1초 ..



먼저 이 문제를 풀기 위해 내가 작성했던 코드의 초기 세팅 과정을 정리해보자면

첫번째
수빈이는 걷거나 순간이동을 할 수 있다.
걷는다면 1초 후에 X -1, X+1로 이동
순간 이동을 한다면 1초 후에 2 * X 로 이동
위 내용을 수행 할 크기가 3인 배열을 만들었다.

두번째
해당 좌표 방문 여부를 저장할 배열, 이동한 거리에 대한 시간을 저장할 배열을 만들었다.

세번째
좌표를 저장할 큐를 만들었다.

초기 세팅은 완료!

코드 설명 시작

1. 수빈이와 동생의 현재 위치 좌표를 입력 받으면 큐에 수빈이의 위치를 넣어준다.

2. 이동한 거리에 대한 시간을 저장할 배열에 현재 수빈이의 위치에 0을 넣어준다.
0을 넣어주는 이유는 아직 이동을 하지 않은 상태이기 때문이다.(0초)

3. 방문 여부를 저장할 배열에서 수빈이의 위치를 true로 저장한다.
이유는 해당 위치에 방문했기 때문이다.

그리고 좌표 저장 큐가 빌 때까지 while 문을 돌게 되는데
while 문 내부에서

1. 현재 위치를 저장할 변수를 만들고 현재 위치를 나타내는 큐의 front 값을 저장한다.
2. 현재 위치를 나타내는 큐를 pop한다.

그 다음엔 현재 위치에서 걷거나 순간 이동 시 위치를 알기 위해
현재 위치를 저장한 변수와 이전 초기 세팅 첫번째에 만들었던 크기 3인 배열을 활용할 것이다.

다음 위치를 계산하기 위해 초기 세팅 첫번째에 만들었던 배열 크기 3 만큼 for 문을 돈다.
for 문을 돌면서 다음 위치를 나타내는 변수를 만들고 해당 변수에 이동할 수 있는 위치를 계산하여 저장한다.

• 다음 위치 = 현재 위치 - 1
• 다음 위치 = 현재 위치 + 1
• 다음 위치 = 현재 위치 * 2

조건 1 : 다음 위치를 계산했을 때 0보다 작거나, 범위로 주어진 100000 보다 큰 경우

• 다음 위치 계산이 잘못되었기 때문에 continue로 다시 for문을 돌도록 했다.

조건 1을 만족하지 않는다면

• 위치 계산이 올바르게 되었기 때문에 통과가 되고, 다음 조건을 검사한다.

조건 2: 이동한 거리에 대한 시간을 저장한 배열이 0이 아니거나, 이미 방문했던 위치인 경우

• continue로 다시 for문을 돌도록 했다.

조건 2를 만족하지 않는다면

• 이동한 거리에 대한 시간을 저장한 배열의 다음위치에 이동한 거리에 대한 시간을 저장한 배열의 현재 위치 + 1를 저장
• 다음 위치를 방문했음으로 방문 여부 확인 배열의 다음 위치에 true로 저장
• 좌표를 큐에 push

 

위 내용을 반복하면서 while문을 빠져나오게 되면
이동한 거리에 대한 시간을 저장한 배열의 동생의 위치에
가장 동생을 빠르게 찾을 수 있는 시간이 담겨져 있어 해당 값을 출력하면 된다.

[최종 코드]

 

[GitHub]

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;


int walk_teleport[3] = { -1, 1, 2 }; // x -1 , x+1, 2*x
int cal_distance[100001]; // 거리 - 초 저장할 배열
bool visited[100001]; // 방문 여부 확인

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int subin, brother; // 수빈이, 동생
    cin >> subin >> brother;
    queue<int> q;
    q.push(subin);
    cal_distance[subin] = 0; // 현재 위치
    visited[subin] = true;
    while (!q.empty()) {
        int curX = q.front();
        q.pop();
        for (int i = 0; i < 3; ++i) {
            int nextX = 0;
            if (i != 2) nextX = curX + walk_teleport[i];
            else nextX = curX * i;
            if (nextX < 0 || nextX > 100000) continue;
            if ((cal_distance[nextX] != 0) || (visited[nextX])) continue;
            cal_distance[nextX] = cal_distance[curX] + 1;
            visited[nextX] = true;
            q.push(nextX);
        }
    }
    cout << cal_distance[brother];
}