백준 1679 - 숨바꼭질 BFS

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

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

 

예제 출력

4

---

문제 풀이

이 문제는 내가 BFS 에 대해서 아직 잘 이해를 못해서 그런거겠지만 솔직히 어려웠다.

물론 중간에 이렇게 푸는 것이 아닐까...? 하면서 비슷하게 풀기도 했는데 4% 에서 틀렸습니다 나오고 10% 에서 틀렸습니다가 나오고ㅠㅠㅠ 결국 고민고민하다가 다른 사람들의 힌트(풀이)보고서야 코드를 짤 수 있었다.

 

이 문제는 2가지로 생각해야한다.

1. 입력받은 n 이 k 보다 크거나 같은 경우

사실 제일 어렵고 젤 생각하기 어려웠던 부분인거 같다. 동시에 정말 간단한 부분이다.

n 이 k 보다 크거나 같은 경우 n 이 k 에 도달하기 위해서 할 수 있는 연산은 n-1 하나뿐이다. 즉 n 이 k 로 도달하기 위해서는 n -k 만큼 n 에서 -1 연산을 해야한다는 것이다.

마찬가지로 n 와 k 가 입력받을 때부터 같은 값이라고 한다면 아무런 연산을 할 필요가 없다. 움직일 필요없이 0 이라는 값이 나와야한다.

정리하자면 n 이 k 보다 크거나 같은 경우 n-k 를 한 값이 곧 정답이 되는것이다.

 

2. ch 배열과 time

ch 배열은 입력받은 n 을 연산한 값과 몇번째 연산인지(몇번 움직였는지) 를 저장하기 위한 배열이다. 정확히는 n 을 연산한 값이 곧 인덱스 번호가 되고, 해당 인덱스의 값에는 몇번째 연산인지(몇번 움직였는지) 를 저장한다.

또한 ch 배열의 값을 맨 처음 0으로 초기화하는 이유는 계산하면서 ch[sum] == 0 인 경우는 방문하지 않은 인덱스이고, ch[sum] !=0 인 경우는 방문한 인덱스로 구분하기 위해서이다.

 

1) n 과 k 에 각각 5와 17 이 들어왔따. n < k 임으로 if 문에 걸리지 않았고, queue 에 n 을 넣고, ch[n] = 1 을 넣는다. 1 을 넣은 이유는 해당 값을 방문했음을 확인하기 위해서이다(사진 노란색)

 

2) findBrother 이 queue 에서 값을 빼서 sum 변수에 저장한다. 이때 나오는 sum 값은 맨 처음 들어간 5 이다. 5가 할 수 있는 연산은 +1, -1, *2 이다. 이를 계산하여 ch[sum-1, sum+1, sum*2] 인덱스에 ch[sum]+1 해서 넣는다. ch[sum]+1 을 하는 이유는 이전 연산 횟수에 +1 하기 위해서이다. 즉 마지막으로 방문한 곳이 ch[sum] 임으로 현재 연산 횟수는 마지막으로 방문한 ch[sum] +1 을 해야하기 때문이다.

 

이에 따라서 각각 ch[4] =2, ch[6] =2, ch[10] = 2 가 된다. 동시에 queue 에 4, 6, 10 을 넣어준다(사진 주황색)

 

3) queue 에는 4, 6, 10 이 들어와 있다. 각각의 값을 꺼내서 연산을 시작한다.

4는 +1, -1, *2 해서 각각 5, 3, 8 이된다. 이때 ch[5] 안의 값이 0 이 아님으로 5로는 가지않고 3, 8 만 방문후 이전 ch[4] 의 값 +1 을 해서 저장한 후 3, 8 을 queue 에 넣는다.

6도 마찬가지로 -1 했을 때 5로는 방문하지 않고 7, 12 만 방문한 후 ch 배열에 값을 저장한 후 queue 에 7, 12 를 넣는다.

10은 +1, -1, *2 모두 이전에 방문하지 않은 채 0 임으로 방문한 후 ch 배열에 값을 저장한 후 11,9,20 을 queue 에 넣는다.

 

4) 3) 에서 했던 과정을 수 계~~~속 반복한다. 그러면 어느 순간에 sum+1, -1, *2 중 하나가 k 값에 도달하는 때가 있다. 이때가 바로 BFS 를 종료하는 시점이다. 이를 위해서 중간에 if(sum+1 ==k || sum-1 == k || sum*2 ==k) 가 존재한다.

이 경우 가장 빠른 시간, 즉 최소 연산 값은 바로 이전에 방문한 ch[sum] 의 값이 된다.

 

5) 이번 문제는 사실 나도 어려워서 다른 사람들의 코드를 보면서 많이 참고하였고, 글보다는 그림으로 봐야 보다 이해가 잘되는 편이라 설명이 좋지 못하다ㅠㅠ

참고 링크를 달아두었으니 다른 분들의 자세하고 좋은 설명 참고 부탁드립니다!!

package baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Quiz_1697_풀이완료 {

    static int n, k; // 입력받은 위치

    static int[] ch = new int[100001]; // 배열의 크기는 최대입력받을 수 있는 크기 +1
    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());
        k = Integer.parseInt(st.nextToken());

        Arrays.fill(ch, 0); // 배열을 0 으로 초기화화

       // 입력받은 n 이 k 보다 크거나 같다면, n-k !!
        // n 이 k 보다 클때 n 이 k 에 도달하기 위해 할 수 있는 연산은 -1 하나뿐이다.
        // 따라서 결국 n 에서 k 까지 -1 을 몇번이나 하는가? 가 답이된다.
        if (n >= k) {
            System.out.println(n - k);
        }else{
            // 아니라면
            // ch 배열에 n 번째 인덱스에 1을 넣고
            // queue 에 n 을 넣고 findBrother 실행!
            ch[n] = 1;
            q.offer(n);

            findBrother();
        }
    }

    static void findBrother() {

        while (!q.isEmpty()) {

            int sum = q.poll(); // q에서 하나의 값 빼내기

            // sum+1, sum-1, sum*2 중 하나의 연산이라도 k 에 도달하면 종료
            if (sum + 1 == k || sum - 1 == k || sum * 2 == k) {
                System.out.println(ch[sum]); // ch[sum] 을 출력 ==> ch[sum] 안에는 시간값이 들어가 있음
                return;
            }

            // 아래의 연산은 모두 동일한 내용
            // +1, -1, *2 했을때 각각 0보다 크거나 같고, 100000보다 작거나 같아야함
            // 동시에 ch[sum+1, sum-1, sum*2] 의 값이 0 이여야함
            // 이는 배열의 초기값이 0 임으로 0 이 아닌 다른 숫자가 들어온 경우 해당 배열을 이미 방문했기 때문에
            // 재방문하여 queue 에 넣을 필요가 없기 때문.

            // 또한 ch 배열에 들어가는 값은 현재 ch[sum] 값의 +1
            // 이는 ch[sum] 의 값이 현재까지 몇번 움직였는지 알 수 있는 값이기 때문
            if (sum +1 <= 100000 && ch[sum + 1] == 0) {
                ch[sum + 1] = ch[sum] + 1;
                q.offer(sum + 1);
            }
            if (sum - 1 >= 0 && ch[sum - 1] == 0) {
                ch[sum - 1] = ch[sum] + 1;
                q.offer(sum - 1);
            }
            if (sum * 2 <= 100000 && ch[sum * 2] == 0) {
                ch[sum * 2] = ch[sum] + 1;
                q.offer(sum * 2);
            }


        }

    }
}

 

---

- Reference

https://velog.io/@kimmjieun/%EB%B0%B1%EC%A4%80-1697%EB%B2%88-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88-Java-%EC%9E%90%EB%B0%94

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

https://propercoding.tistory.com/15

[백준] 1697번 : 숨바꼭질 – JAVA [자바]