JAVA [Algorithm] - 백준 1697 숨바꼭질

 

📝문제 설명

 

- 처음에는 그리디 알고리즘인 줄 알고 그리디로 접근하려 했지만 매 순간 최적의 선택(2*x로 갈 때)을 하더라도 최단 거리를 보장할 수 없을 것 같아 BFS로 접근해보았다.

 

- 수빈이가 이동할 수 있는 경우 : X-1, X+1, 2*X

- 0초일 때 : X위치

- 1초 후일 때 : X-1, X+1, 2*X

 

- 수빈이의 위치를 배열의 인덱스로 정하고 해당 인덱스 값에 초를 기입한다. 배열의 기본 값은 0이기 때문에 초는 +1을 해주며 결과값을 도출 할 때는 -1을 해줄 예정

- 가장 빠른 시간을 구하는 것이 목적이기 때문에 위치를 이동했다가 다시 방문할 때는 값을 변경하지 않는다.

 

수빈이 위치 : 5

동생 위치 : 17

 

0초일 때

수빈이의 위치를 배열의 인덱스 값으로 정한다고 했으니 인덱스 5번 위치에 0초일 때 위치를 1로 기입한다.

 

1초일 때

1초일 때 갈 수 있는 인덱스는 (4, 6, 10)이다. 

 

2초일 때

큐 4의 값을 빼고 4의 경우의 수에 해당하는 인덱스에 초들을 기입, 큐에 추가

 

큐의 6의 값을 빼고 6의 경우의 수에 해당하는 인덱스들에 초들을 기입, 큐에 추가

 

큐의 10의 값을 빼고 6의 경우의 수에 해당하는 인덱스들에 초들을 기입 후, 큐에 추가

 

3초일 때

큐의 3의 값을 빼고 3의 경우의 수에 해당하는 인덱스들에 초들을 기입 후, 큐에 추가

큐의 8의 값을 빼고 8의 경우의 수에 해당하는 인덱스들에 초들을 기입 후, 큐에 추가

 

큐의 7의 값을 빼고 7의 경우의 수에 해당하는 인덱스들에 초들을 기입 후, 큐에 추가

 

큐의 12의 값을 빼고 12 경우의 수에 해당하는 인덱스들에 초들을 기입 후, 큐에 추가

 

위 방법대로 진행하다 보면

 

이런 식으로 배열에 형석되게 되는데

 

큐의 18의 값을 빼고 18 경우의 수에 해당하는 인덱스들에 초를 기입 후, 큐에 추가하면

 

17값이 큐에 들어오게 된다.

17값이 큐에 들어오면 도착지점과 같아지므로 17인덱스에 해당하는 값에 -1을 해주고 return 하면 된다.

---

📢입출력 예시

 

---

✏️문제 풀이

package Baekjoon.Graph.BFS;

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 Baek1697 {

    static int N,K;
    static int[] visited = new int[100001];

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        N = Integer.parseInt(stringTokenizer.nextToken());
        K = Integer.parseInt(stringTokenizer.nextToken());

        System.out.println(BFS(N));
    }

    private static int BFS(int node){
        Queue<Integer> queue = new LinkedList<>();

        queue.offer(node);
        visited[node] = 1;

        while (!queue.isEmpty()) {
            int n = queue.remove();

            if (n == K) {
                return visited[n]-1;
            }

            if (n-1>=0 && visited[n-1] == 0) {
                visited[n-1] = visited[n]+1;
                queue.add(n-1);
            }
            if (n+1 <= 100000 && visited[n+1] == 0) {
                visited[n+1] = visited[n]+1;
                queue.add(n+1);
            }
            if (2*n <= 100000 && visited[2*n] == 0) {
                visited[2*n] = visited[n] + 1;
                queue.add(2*n);
            }
        }
        return -1;
    }
}

---

💡새로 알게된 점

 

처음 방문 배열을 도착 지점과 같게 설정해서 인덱스 범위에 오류가 났다!!

---