[백준] 1697번: 숨바꼭질

https://www.acmicpc.net/problem/1697

 

 

 

문제 파악

- 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.

<알고리즘 분류>
-그래프 이론
-그래프 탐색
-너비 우선 탐색

 

접근 방법

-최소시간을 구해 리턴해야 하므로 BFS접근을 사용한다.

-정수 배열을 담는 큐 자료형 사용

-정수 배열에는 수빈이의 위치 x와 걸린 시간이 담긴다.

 

 

코드 구현

package com.baekjoon;

public class p1697_숨바꼭질 {
    public static int p1697_숨바꼭질() 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 MAX = 100000;
        boolean[] visited = new boolean[MAX];//각 방문 경로마다 발자취 남기기(갔던 길 또 못감)
        //최단거리 큐
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{n,0});
        visited[n] = true;
        while(!queue.isEmpty()){
            int[] node = queue.remove();
            int path = node[0];
            int time = node[1];

            if(path==k){
                return time;
            }

            int[] toGo = new int[]{path+1,path*2,path-1};
            for(int x:toGo){
                if(x>=0 && x<=MAX && !visited[x]){
                    queue.add(new int[]{x,time+1});
                    visited[x] = true;
                }
            }
        }
        return -1;
    }



    public static void main(String[] args) throws IOException {
        int result = p1697_숨바꼭질();
        System.out.println(result);
    }


}

 

 

배우게 된 점

노드를 제거할 때 방문하는 방식이 아닌, 노드를 삽입할 때 방문 체크를 해주는 것이 참신했다.

왜 노드를 삽입할 때 이례적으로 방문 체크를 해줄까? 실제로 노드 제거 시, 평소처럼 방문 체크해주니 컴파일 에러 발생.

챗 GPT에게 물어봤다.

 

이론적으로 큐에서 노드를 뺄 때 방문 처리를 해도 결과는 동일할 수 있습니다. 하지만 큐에 넣을 때 방문 처리를 하는 방식이 더 효율적입니다. 그 이유는 다음과 같습니다.

차이점:

1. 큐에 중복 노드가 여러 번 들어가는 문제:
   • 큐에서 방문 처리를 하는 경우, 중복된 노드가 여러 번 큐에 들어갈 수 있습니다. 예를 들어, 수빈이가 n에 있을 때, n + 1, n - 1, n * 2로 이동할 수 있는데, 방문 처리를 하지 않고 큐에 넣으면 중복된 값들이 여러 번 큐에 들어갈 가능성이 있습니다.
   • 만약 n + 1을 여러 경로로 갈 수 있다면 큐에서 해당 위치를 여러 번 꺼내야 할 수 있습니다.
2. 불필요한 큐 크기 증가:
   • 큐에 중복된 노드가 들어가면, 큐의 크기가 커져 메모리 사용량이 증가하고, 중복된 노드를 처리해야 하기 때문에 CPU 시간이 더 소모됩니다.
   • 큐에서 중복된 노드를 꺼낼 때는 방문 처리를 한다고 해도, 그 노드를 큐에 넣는 과정에서 메모리와 시간을 낭비할 수 있습니다.
3. 큐에서 방문 처리를 하면 탐색 속도가 느려질 수 있음:
   • 큐에서 방문 처리를 하게 되면, 큐에 이미 같은 노드가 여러 번 들어가므로, 방문 처리가 이뤄질 때마다 해당 노드의 처리가 반복됩니다.
   • BFS에서는 같은 노드를 여러 번 처리할 필요가 없으므로, 큐에 넣을 때 방문 처리를 하면 큐의 크기를 줄여 불필요한 중복 탐색을 방지할 수 있습니다.

 

 

즉, x+1이나 x-1이나 x*2이나, 이 연산 값들 중 중복이 있을 수도 있다는 것이다!

그럼, 같은 값을 굳이, 넣을 필요가 없으니

애초에 반복문 돌면서 큐에 넣을 때, 제해버리자는 것이다.