[코딩테스트] 백준 1697번 숨바꼭질 - JAVA

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

Problem 💻

문제

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

 

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

 

입력

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

 

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

Solution 💡

수빈이랑 동일한 한 라인(선) 위치에 있고 수빈이는 다음과 같은 조건으로 이동한다.

• 1초 기준 +1, -1 이동
• 1초 기존 x2만큼 이동

위 조건을 기준하에 수빈이가 동생을 몇 초 만에 잡을 수 있을지 구하는 문제이다. 이 문제는 1초 움직임마다 가중치(시간비용)가 주어진 최단 경로를 찾는 문제이다.

 

이런 최단 경로를 찾는 문제는 BFS가 기본베이스가 된다. BFS에 경우 탐색의 순서와 가까운 노드부터 탐색하므로 같은 레벨(동생의 위치)에 처음 도달한 순간이 자연스럽게 최적에 경로가 된다.

 

기본 BFS 코드를 기반으로 진행된다.

1. 큐를 활용하였고, int[] 배열로 초기화하여 {현재위치, 시간} 형태로 데이터 구조를 잡았다.
2. 큐에 수빈이의 첫 위치 값을 start값으로 잡아 시작한다.
3. 큐가 끝날 때까지 루프를 돌면서 안에 1초에 따른 가중치에 대한 로직을 실행한다.
4. 가중치값을 업데이트한 nx가 유효한 위치에 대한 판단이 되면 큐에 추가하고 방문처리 한다.
5. 단, nx가 동생의 위치가 되면 리턴을 해준다. (BFS 사용이유 - 값에 도달하는 첫 순간이 최적에 경로가 된다.)

package backjoon.silver.lv1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class B1697 {
    public static void main(String[] args) throws IOException {
        // 입력 처리
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        // 시작 위치와 도착 위치가 같은 경우
        if (start == end) {
            System.out.println(0);
            return;
        }

        // BFS 초기 설정
        int[] dx = {-1, 1, 2}; // 이동 방향
        boolean[] visited = new boolean[100001]; // 방문 여부
        Queue<int[]> queue = new LinkedList<>();
        
        // 시작 위치 추가
        queue.add(new int[]{start, 0});
        visited[start] = true;

        // BFS 탐색
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int location = current[0];
            int time = current[1];

            // 이동 가능 위치 탐색
            for (int i = 0; i < 3; i++) {
                int nx = (i == 2) ? location * dx[i] : location + dx[i];

                // 유효한 위치인지 확인
                if (nx >= 0 && nx < 100001 && !visited[nx]) {
                    // 도착지점에 도달한 경우
                    if (nx == end) {
                        System.out.println(time + 1);
                        return;
                    }

                    // 큐에 추가하고 방문 처리
                    queue.add(new int[]{nx, time + 1});
                    visited[nx] = true;
                }
            }
        }
    }
}

 

여기서 내가 놓였던 부분은 수빈이랑 동생이 같은 값일 경우였다. 예제는 답이 나오는데 계속 틀릴 경우 이런 기본적인 요소를 확인해야 될 것 같다.

아래 코드와 같이 둘이 같은 경우 0을 출력하는 구문을 추가하니 정답처리가 되었다.

// 시작 위치와 도착 위치가 같은 경우
if (start == end) {
    System.out.println(0);
    return;
}