[백준] no1697: 숨바꼭질

문제

N: 출발좌표

K: 도착좌표

1번에 움직일 수 있는 방법은 현재 좌표로 부터 +1, -1, *2

 

문제 링크 : https://www.acmicpc.net/problem/1697

---

원리

여러 방법이 있으나, 일반적인 방법은 BFS이다.

예시 : 5와 17이 주어질 경우, 5 -> 4 -> 8-> 16 -> 17 로 총 4번만에 갈 수 있다.

---

풀이방법

1.  출발점보다 도착점이 클 경우, -1의 반복으로만 도달 가능 = 출발점-도착점

2. 그 외의 경우 BFS 탐색

3. 각 경우에 따른 연산을 순차적으로 넣어줄 대기열(Deque가 제일 빠름)을 만들어줌

4. 몇번 이동했는지 적어줄 배열(subin)을 선언.

5. 첫 출발점을 대기열에 넣어주고, 첫 출발점 인덱스에 count=1을 넣어줌

6. 대기열이 빌 때까지 반복

    (단, 내부 로직에서 처음으로 목표지점과 동일하여 도착하는 경우가 가장 최소count이므로 중간에 멈출 수 있음)

7. 현재 연산할 값을 대기열에서 꺼냄

8. 각 연산방법 (-1, +1, *2)를 순차적으로 시도할 것임(for문으로 3번 돎)

9. 각 연산마다 계산값이 목표값이랑 일치하는지 확인함. 일치하면 배열에 넣어둔 count값을 반환

10. 일치하지 않는 경우, 이동 가능한 범위에 한해서 다음으로 연산할 지점을 대기열에 넣어주고, count+1함

 

---

나의 코드

1. 둘 사이의 거리의 절대값만큼 2로 나누어 접근하는 방법 -> 다양한 이동방법을 생각 못했고, 홀수일 경우 문제가 발생

: 애당초 문제를 잘못 이해했다.

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

public class Main {

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

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N= Integer.parseInt(st.nextToken());
        int M= Integer.parseInt(st.nextToken());

        int distance = Math.abs(N-M);
        int count = 0;
        while(distance!=1) {
            distance /=2;
            count++;
        }
        System.out.println(count+1);
    }
}

 

2. 최대한 목표지점에 가깝게 순간이동만 한 후 남은 거리만큼 걸어서 이동

: 후진 -> 순간이동 -> 전진 등 다른방식의 접근법을 간과했다. 

package class1.src;

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

public class no1697 {

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

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N= Integer.parseInt(st.nextToken());
        int K= Integer.parseInt(st.nextToken());

        int count = 1;
        // N이 K에 인접해질때까지 순간이동
        while(true) {
            if(2*count*N>=K) break;
            count++;
        }

        // K가 count번 순간이동 한 좌표와 같을 땐, count가 곧 이동횟수
        // K가 count번 순간이동 한 좌표보다 작을 때 (즉, 순간이동을 오버해서 했을 때)
        // 만약 한번 순간이동 덜 했을 경우(before)와 한번 순간이동을 더 오버해서 했을 때(after) 중,
        // K와의 거리가 더 가까운 횟수를 골라서 K와의 간격만큼 더해준다.
        if(2*count*N>K) {
            int after = Math.abs(2*count*N - K);
            int before = Math.abs(2*(count-1)*N - K);
            if(after > before) count += before;
            else count += after;
        }

        System.out.println(count);
    }
}

 

3. 재귀 : StackOverflow 발생 -> 그럴만 했음

package class1.src;

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

public class no1697 {
    static int N;
    static int K;
    static Integer min;

    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());
        min = Integer.MAX_VALUE;

        recur(N, 0);

        System.out.println(min);
    }

    private static void recur(int start, int cnt) {
        if(start==K) {
            if(min>cnt) min = cnt;
            return;
        }
        else if(start>K) {
            int remains = start - K;
            if(min>cnt+remains) min = cnt+remains;
            return;
        }
        else {
            recur(start*2, cnt+1);
            recur(start-1, cnt+1);
            recur(start+1, cnt+1);
        }
        return;
    }
}

 

4. BFS : 반복하며 구해야 할 경우의 수를 모두 대기열(Deque)에 넣고 완전탐색

* 만약 출발점이 목표점보다 클경우, 무조건 -1을 반복하여 도달하는 방법밖에 없다는 점을 놓치면 안됨

static int N;
static int K;

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(N-K); // 만약 출발점이 목표점보다 크면 무조건 -1의 반복으로만 도달할 수 밖에 없음
    else System.out.println(BFS(N, K));
}

private static int BFS (int start, int goal) {
    Deque<Integer> dq = new ArrayDeque<>();
    int[] count = new int[100001];  // 수빈이가 움직일 수 있는 최대 지점까지 인덱스

    dq.add(start);
    count[start] = 1;

    // 한 번에 많은 연산을 하지 않도록, 각각의 경우를 dq에 넣고 계산.
    // dq.isEmpty() = true이면, 모든 탐색이 끝난 것
    // 중간에 목표값과 같은 값이 나오면, 가장 적은 수의 움직임을 count한 경우이므로, 해당 지점에서 return으로 종료가능
    while(!dq.isEmpty()) {
        int now = dq.poll();

        // 3가지 경우를 계산
        for(int i = 0 ; i<3 ; i++) {
            int next;

            if(i==0) next = now - 1;
            else if(i==1) next = now + 1;
            else next = now * 2;

            if(next == goal) return count[now]; // subin배열의 인자는 곧 count. 첫번째에 이미 1을 넣고 시작했으므로, next까지 카운트 된 상태

            // now를 next로 업데이트 해주며, count 배열의 count를 1씩 올려주는 구간
            // 수빈이의 최대 이동거리는 100000까지이므로, 그 안에서 해결
            if(0 <= next && next <= 100000) {
                if(count[next] == 0) {
                    dq.add(next);
                    count[next] = count[now] + 1;
                }
            }
        }
    }
    return 0;
}

---

레퍼런스 코드

참고 링크 : https://bcp0109.tistory.com/61