[BOJ] 백준 1697 숨바꼭질

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

1697번: 숨바꼭질

 

---

 

풀이 과정

1. 총 3가지의 경우를 탐색해야 한다. 위치가 X일 때, X-1과 X+1, X*2 이렇게 세 가지.
2. int형 checked라는 배열을 만들어서 거쳐온 거리(도착하기까지 걸린 시간)를 기록한다.
3. bfs를 사용해서 시작점인 n부터 큐에 넣고, 만들어둔 배열 인덱스 n에 대한 값으로 방문했다는 의미로 1이라는 값을 넣는다.
4. 반복문을 돌려서 세 가지 경우를 모두 탐색하고 탐색한 결과 값과 k가 같아지는 순간, checked[큐에서 꺼낸 값]을 출력하는 동시에 리턴한다.

풀이 과정을 토대로 그림을 그려 봤다. start(수빈이의 위치)가 5, end(동생의 위치)를 11로 가정하고 진행한다.

시작점을 거리에서 제외하기 위해 이전 값인 2를 출력해야 한다. 

 

다음은 Java로 작성한 코드이다.

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 Main {
    private static int n, k;
    private static final int [] checked = new int[100001];

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

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        if (n == k) {
            System.out.println(0);
        } else {
            bfs();
        }
    }

    private static void bfs() {
        Queue<Integer> q = new LinkedList<>();
        q.add(n);
        checked[n] = 1;

        while (!q.isEmpty()) {
            int temp = q.poll();

            for (int i = 0; i < 3; i++) {
                int next;

                if (i == 0) {
                    next = temp + 1;
                } else if (i == 1) {
                    next = temp - 1;
                } else {
                    next = temp * 2;
                }

                if (next == k) {
                    System.out.println(checked[temp]);
                    return;
                }

                if (next >= 0 && next < checked.length && checked[next] == 0) {
                    q.add(next);
                    checked[next] = checked[temp] + 1;
                }
            }
        }
    }
}