[알고리즘][X] 숨바꼭질

https://www.acmicpc.net/submit/1697/72246857

로그인

import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    private static class Node {
        private final int time;
        private final int position;

        public Node(int time, int position) {
            this.time = time;
            this.position = position;
        }

        public int getTime() {
            return time;
        }

        public int getPosition() {
            return position;
        }
    }
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int K = scanner.nextInt();

        if (N==K) {
            System.out.println(0);
            return;
        }
        Node node = new Node(1, N);
        // 최단 거리이기 때문에 BFS로 구현 가능하다.
        int LeastTime = bfs(node, K);
        System.out.println(LeastTime);
    }

    private static int bfs(Node node, int k) {
        Queue<Node> queue = new LinkedList<>();

        int[] dx = {-1, 1, 2};
        boolean[] visited = new boolean[100001];
        queue.offer(node);
        visited[node.getPosition()] = true;
        while (!queue.isEmpty()) {
            node = queue.poll();
            for (int j : dx) {
                int nextPosition;
                if (j == 2) {
                    nextPosition = 2 * node.getPosition();
                } else {
                    nextPosition = node.getPosition() + j;
                }

                if (nextPosition == k) {
                    return node.getTime();
                }

                if (nextPosition >= 0 && nextPosition < 100_001 && !visited[nextPosition]) {
                    queue.offer(new Node(node.getTime() + 1, nextPosition));
                    visited[nextPosition] = true;
                }
            }

        }

        return 0;
    }
}

나의 풀이

- if문에서 100,000이 아니라 100,001까지 가능한데 경계값 처리를 잘못했다.

 

아래는 처음 위치가 K일때 예외 처리 코드를 while 문 안으로 통합하였다. 그 결과 가독성이 더 좋아졌다.

import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    private static class Node {
        private final int time;
        private final int position;

        public Node(int time, int position) {
            this.time = time;
            this.position = position;
        }

        public int getTime() {
            return time;
        }

        public int getPosition() {
            return position;
        }
    }
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int K = scanner.nextInt();

        if (N==K) {
            System.out.println(0);
            return;
        }
        Node node = new Node(0, N);
        // 최단 거리이기 때문에 BFS로 구현 가능하다. 
        // 시간 복잡도 O(V+E)인데 정확하게 계산이 어렵다.
        // 수기로 해보면 O(2V)는 안되는 듯하다.
        int LeastTime = bfs(node, K);
        System.out.println(LeastTime);
    }

    private static int bfs(Node node, int k) {
        Queue<Node> queue = new LinkedList<>();

        // 요 부분을 어떻게 하면 직관적으로 할 수 있을까?
        int[] dx = {-1, 1, 2};
        boolean[] visited = new boolean[100001];
        queue.offer(node);
        visited[node.getPosition()] = true;

        while (!queue.isEmpty()) {
            node = queue.poll();
            if (node.getPosition() == k) {
              return node.getTime();
            }
            for (int j : dx) {
                int nextPosition;
                if (j == 2) {
                    nextPosition = 2 * node.getPosition();
                } else {
                    nextPosition = node.getPosition() + j;
                }

                if (nextPosition >= 0 && nextPosition < 100_001 && !visited[nextPosition]) {
                    queue.offer(new Node(node.getTime() + 1, nextPosition));
                    visited[nextPosition] = true;
                }
            }

        }

        // 못 찾는 경우
        return -1;
    }
}