[BOJ] 12851번 - 숨바꼭질2 (Java)

🛠️ 문제 🛠️

---

🗒️ 설명 🗒️

이번 문제에서 내가 잘못 생각했던 부분에 대해 기록해두려고 한다.

우선 기억해야할 것은 BFS는 무방향 그래프에서 최단경로를 구할 수 있다.

즉, 처음 동생의 위치에 도착하면(answer = 0) 그 때 시간이 최소시간이 된다.

 

여기까지만 생각하고 작성한 코드 중 queue 삽입과 관련된 코드이다.

메모리 초과 코드

위와 같이 단지 next위치에서 도달한 시간이 최소 시간보다 작으면 무조건 queue에 넣도록 했다. 

하지만 메모리 초과가 발생했고 그 이유에 대해 생각해보았다.

현재 코드로는 도착지점과 현재 지점의 거리와 상관없이 현재 시간이 최소 시간보다 작으면 무조건 큐에 삽입했다.

그러면 절대 최소시간에 도착할 수 없는 경우도 큐에 존재하며 메모리 초과가 발생할 수 있다.

최악의 경우를 생각해보면 queue에서 1개를 빼고 3개가 들어가 2개씩 쌓이는 상황이 계속 발생할 것이다.

만약 동생과 수빈이의 위치가 매우 큰 차이를 가지고 있으면 당연히 queue의 길이는 매우 길어질 것이다.

 

메모리를 덜 사용하기 위해 할 수 있는 방법은 큐에 삽입하는 조건을 추가해주는 것이다.

도착 지점뿐만 아니라 현재 위치까지도 최소 시간으로 도달해야 도착까지 최소 시간이 걸릴 가능성이 있다.

즉, 현재 위치까지 어떤 방식으로 도달하더라도 최소 시간이기만 하면 된다는 것이다.

visited 배열을 만들어 현재 정점에 도달하는 최소 시간을 기록해둘 수 있도록 했다.

위에서 BFS의 특성을 말했듯이 현재 정점에 도달한 순간 그 시간이 최소시간이 될것이다.

visited = 0일 경우 방문 하지 않았으므로 현재 도착한 시간이 최소시간이 되므로 이를 기록해두록 했다.

재방문할 때(visited != 0) 현재 저장되어 있는 최소 시간에 도달했을 경우에만 큐에 삽입하도록 하여 삽입 조건을 추가했다.

정답 코드

---

🍀 풀이 🍀

package Baekjoon;

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

public class Graph12851 {
    public static class Node {
        int x, time;
        public Node(int x, int time) {
            this.x = x;
            this.time = time;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        if(start >= end) { //만약 수빈이가 동생보다 앞에 있을 경우 뒤로만 가는 방식으로 도착
            System.out.println(start-end);
            System.out.println(1);
            return;
        }
        bfs(start, end);
    }

    /**
     * 최소 시간과 방법의 개수 출력하는 함수
     * @param s 수빈이의 시작 위치
     * @param e 동생이 있는 도착 위치
     */
    public static void bfs(int s, int e) {
        int answer = 0;
        int minTime = Integer.MAX_VALUE;
        int[] visited = new int[100001];

        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(s, 0));

        while(!queue.isEmpty()) {
            Node current = queue.poll();

            if(minTime < current.time) {
                continue;
            }

            if(current.x == e) {
                if(answer == 0) { //BFS는 최단경로를 구하기 때문에 처음에 도달한 경우가 최소 시간
                    minTime = current.time;
                }

                if(current.time == minTime) {
                    answer++;
                    continue;
                }
            }

            int[] next = {current.x-1, current.x+1, current.x*2};
            for(int i = 0; i < 3; i++) {
                if(next[i] < 0 || next[i] > 100000) {
                    continue;
                }

                //0일 경우 방문한 적이 없으므로 현재 시간이 최소 시간
                //현재 정점에 최소시간으로 도달해야 동생의 위치까지 최소로 올수 있는 가능성 존재
                if(visited[next[i]] == 0 || visited[next[i]] == current.time + 1) {
                    visited[next[i]] = current.time + 1;
                    queue.offer(new Node(next[i], current.time+1));
                }
            }
        }

        System.out.println(minTime);
        System.out.println(answer);
    }
}