[알고리즘 PS] 백준 1697번 숨바꼭질 자바 문제풀이

문제

해당 포스팅은 백준의 1697번 숨바꼭질 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

1697번: 숨바꼭질

 

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

 

문제 접근

 

이 문제는 BFS 와 방문 처리를 이용한다면 쉽게 해결할 수 있는 문제이다.

 

해결법

 

bfs로 각각의 케이스에 대해서 확인을 한다.

 

1. 현재 거리에서 - 1 한 경우
2. 현재 거리에서 + 1 한 경우
3. 현재 거리에서 * 2 한 경우

 

각각의 경우를 queue 에 넣고 bfs 를 진행하면 된다.

 

최단 시간은 queue 에 넣을 때가 가장 최단의 시간 이라고 보고 해당 시간에서 + 1을 한 값을 넣어주면 된다.

 

정답 코드

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] nk = br.readLine().split(" ");

        int n = Integer.parseInt(nk[0]);
        int k = Integer.parseInt(nk[1]);

        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        int[] visited = new int[100_001];

        for (int i = 1; i < 100_001; i++) {
            graph.add(new ArrayList<>());
        }

        Queue<Integer> queue = new LinkedList<>();

        visited[n] = 0;
        queue.add(n);

        while(!queue.isEmpty()) {
            int front = queue.remove();

            if(front == k) {
                System.out.println(visited[front]);
                break;
            }

            int[] next = {front + 1, front - 1, front * 2};

            for (int i = 0; i < next.length; i++) {
                if(0 <= next[i] && next[i] <= 100_000) {
                    if(visited[next[i]] == 0) {
                        visited[next[i]] = visited[front] + 1;
                        queue.add(next[i]);
                    }
                }
            }
        }

        bw.flush();
        bw.close();
    }
}

 

---

 

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.