[Java, 자바] 백준 1697번, 숨바꼭질

백준 1697번

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

난이도 : 실버1

---

문제내용

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

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

---

입력

 

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

 

---

출력

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

---

풀이방법

 

이번 문제는 BFS를 통해 해결하였습니다 :)

거리의 범위는 0부터 100000까지 이동을 할 수 있어 방문 배열을 100001크기로 먼저 생성해 놓고, 뒤로 한칸, 앞으로 한칸, 현재 위치에서 X 2 이동할 수 있어 move 배열을 생성해 주었습니다.

시작 지점과 도착 지점이 같을 경우 0을 출력하였고 같지 않을 경우 BFS메서드를 호출하였습니다.

자바에서의 BFS의 핵심은 큐를 이용하여 해결하는 점 ! 

먼저 방문 배열인 ch배열에 시작 지점의 인덱스를 1초 로기화 해놓은 이후 앞으로, 뒤로, X2 총 3개의 경우의 수를 구하기 위해 while문 내에서 반복문을 3번 진행하였으며, 지점을 이동하였을 때 방문 배열을 이전 시작점에서의 값에서 1을 더해주었습니다.

이유는 이동횟수를 확인하기 위해 ! 

이동한 지점이 도착 지점과 같을 때 도착 지점으로 가기전의 카운트 수를 출력하여 마무리하였습니다 :)

---

코드

import java.util.*;
import java.io.*;

public class Main {
    static int n, m;
    static int[] ch = new int[100001];
    static int[] move = {-1, 1, 2};
    static Queue<Integer> Q = new LinkedList<>();

    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());
        m = Integer.parseInt(st.nextToken());
        if (n == m) System.out.println(0);
        else bfs(n);
    }

    public static void bfs(int v) {
        ch[v] = 1;
        Q.offer(v);
        while (!Q.isEmpty()) {
            int size = Q.size();
            for (int x = 0; x < size; x++) {
                int target = Q.poll();
                for (int i = 0; i < 3; i++) {
                    int nv;
                    if (i == 2) nv = target * move[i];
                    else nv = target + move[i];
                    if (nv == m) {
                        System.out.print(ch[target]);
                        return;
                    }
                    if (nv >= 0 && nv < 100001 && ch[nv] == 0) {
                        Q.offer(nv);
                        ch[nv] = ch[target] + 1;
                    }
                }
            }
        }
    }
}