BOJ_1697 : 숨바꼭질

👉 문제링크

1697번: 숨바꼭질

---

---

🔸 문제 분석 🔸

• 0부터 10만까지 범위에서, 수빈이의 위치 N 부터 동생의 위치 K로 이동하는 최단 시간을 출력한다.
  • 수빈이가 이동하는 방법은 좌우 한칸(-1, +1), 순간이동 (현위치 *2)가 있다.
• 주의 할 점은 이동위치와 k의 거리 차이가 가장 적은 것을 선택하는 그리디 방식으로 계산해서는 안된다.
  • 그리디로 보면 예제 1번에서 5 - 10 - 9 - 18 - 17 에서 2번째 이동 할 때인 10위치에서 순간이동이 절댓값 차이가 3으로 가장 적은데, 정작 최단 거리는 왼쪽 이동(-1) 후 순간이동이 더 빠르다.
  • 따라서 모든 경로를 보면서 그 중 최단 경로를 구해야 하므로 BFS를 사용해야 한다.

🔸 코드 🔸

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();
        boolean[] visit = new boolean[100_001];

        Queue<Subin> que = new ArrayDeque<>();
        Subin subin = new Subin(n, 0);

        que.add(subin);

        while (!que.isEmpty()) {
            if ((subin = que.poll()).x == k) {
                break;
            }

            visit[subin.x] = true;

            if (subin.x - 1 >= 0 && !visit[subin.x - 1]) {
                que.add(new Subin(subin.x - 1, subin.ct + 1));
            }
            if (subin.x + 1 <= 100_000 && !visit[subin.x + 1]) {
                que.add(new Subin(subin.x + 1, subin.ct + 1));
            }
            if (subin.x * 2 <= 100_000 && !visit[subin.x * 2]) {
                que.add(new Subin(subin.x * 2, subin.ct + 1));
            }
        }
        System.out.println(subin.ct);
    }

    private static class Subin {
        int x, ct;

        Subin(int x, int ct) {
            this.x = x;
            this.ct = ct;
        }
    }
}

🔸 코드 해석 🔸

• 수빈이의 현재 위치와 카운트를 저장할 수 있도록 Subin 클래스를 만들었다.
• 여러번 계산하지 안도록 boolean 배열 visit을 만들고, N위치부터 BFS를 돌린다.
  • n == k 가 되면 반복을 종료하고 현재 카운트를 출력한다.

 

🔸 조금 다른 풀이 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static final int MAX = 100_000;
    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());

        System.out.println(bfs(N, K));
    }

    private static int bfs(int n, int k){
        boolean[] visit = new boolean[MAX + 1];

        Queue<Subin> que = new ArrayDeque<>();
        que.offer(new Subin(n, 0));
        visit[n] = true;


        while (!que.isEmpty()) {
            Subin subin = que.poll();

            int index = subin.index-1;
            int time = subin.time+1;

            // 왼쪽
            if (0<= index && index <= MAX && !visit[index]){
                if (index == k) return time;
                que.offer(new Subin(index, time));
                visit[index] = true;
            }

            // 오른쪽
            index = subin.index+1;
            if (0<= index && index <= MAX && !visit[index]){
                if (index == k) return time;
                que.offer(new Subin(index, time));
                visit[index] = true;
            }

            // 순간이동
            index = subin.index*2;
            if (0<= index && index <= MAX && !visit[index]){
                if (index == k) return time;
                que.offer(new Subin(index, time));
                visit[index] = true;
            }
        }
        return -1;
    }

    private static class Subin {
        int index, time;

        public Subin(int index, int time) {
            this.index = index;
            this.time = time;
        }
    }
}

• 큐에 넣기 전에 정답인지 확인하는 방식이다.
• 주의 할 점은 n == k 상태로 시간이 0초인 경우이다.
  • while문 안에서는 변한 값을 비교하므로, 큐에 넣기 전 n과 k를 확인해야 한다.

---

🔸 end 🔸

• 처음 문제를 보자마자 그리디라고 생각하고, while문 안에서 절댓값을 비교하는 방식으로 구현했는데 예제 1번에서 틀렸다는 것을 알아챘다.
  • 아직 그리디 부분이 많이 부족한 것 같다.
• 문제 분석과 코딩 계획을 적어가며 문제를 풀었다.
  • 그리디가 틀렸다고 파악한 후로 브루트 포스와 BFS를 생각했다.
  • 따로 다시 코딩 계획을 적진 않았다.
• 2회차로 다시 풀어서, 큐에 넣기 전에 정답을 확인하는 방식으로 풀이했다.
  • 정답이 0초 일때를 처리하지 않아서 1회 틀렸다.