[99클럽 코테 스터디 7일차 TIL / 백준] 1697 - 숨바꼭질 (JAVA)

99클럽 코테스터디 7일차 TIL
KeyWord : BFS, DP, 최단 거리

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

---

 

풀이

어떤 방법으로 접근해야 해결할 수 있을지 고민되었던 문제이다. 적합하다고 생각되는 방법론이 꽤 많았기 때문이다.

• 이분탐색
• 그리디
• DFS
• BFS
• DP

괜찮을 것 같은 방법론은 이 정도였다. 이제 차례대로 검토해보자.

 

이분탐색?

범위가 $0$ ~ $100000$으로 정해져 있으므로 가능할 듯 싶었다.

lo는 수빈이와 동생의 위치가 같을 경우인 0, hi는 수빈이가 0, 동생이 100000일 때 수빈이가 무조건 1칸씩만 움직여서 이동할 경우인 100000으로 잡는다.

여기서 이분탐색으로 해를 구할 수 있을까? 이분탐색을 조금씩 진행해보자.

5 17

이렇게 입력이 주어졌을 때, 첫 mid는 11이 된다. 그런데 여기서 lo와 hi를 어떻게 움직여야 해를 구할 수 있을까?

그저 문제가 17까지의 최소 이동횟수를 구하는 것에서 mid까지의 최소 이동 횟수를 구하는 것이 되어버리는 상황이 만들어졌다.

결론. 이분탐색으로는 안 될 듯하다.

 

그리디?

그리디 알고리즘은 현재 주어진 조건에서 최선의 선택을 하여 문제의 해까지 도달하는 방법이다.

그렇다면 생각해보자.

수빈이의 시작 시점인 $5$에서 어떻게 움직여야 최선의 선택이 되는 걸까? 2배를 하면 가장 많이 이동되므로 이게 최선의 선택일까?

하지만, 5 → 10 → 9 → 18 → 17 이렇게, 가끔은 뒤로 움직인 후에 두 배를 하거나, 한 칸 앞으로 가는 것이 최선의 선택인 경우도 있는데?

결론. 현재 시점에서 무엇이 최선의 선택인지 알수 있는 방법이 없으므로 그리디도 안 될 듯하다.

 

DFS

일단 DFS로 풀려면 그래프여야 하지 않나? 그런 의문이 들 수도 있다.

먼저, 그래프에 대해서 생각해볼 필요가 있는데, 사실 그래프면 노드끼리 연결이 되어 있는가를 중점으로 생각하면 된다.

이 문제에서 노드는 위치일 것이고, 간선은 이동 방법이 될 것이다.

5 12

이런 입력이 들어왔을 때를 그래프로 표현하면 이렇게 된다.

즉, 이 문제도 그래프로 표현할 수 있다.

그렇다면 DFS를 이용하여 최단 거리를 찾을 수 있을까?

찾을 수는 있다. 하지만 모든 경우의 수를 탐색한 후에야 이것이 최단 거리인지 알 수 있다. 이 문제와 같은 경우에는 최대 100000까지 깊이가 쌓일 수 있으므로 메모리 초과가 나타나거나, 시간 초과가 나타날 것이다.

이 문제 기준으로 $O(3^N)$라는 시간 복잡도의 알고리즘이 만들어진다.

결론. 효율성 측면에서 DFS도 제외.

 

BFS

최단 거리 알고리즘에 대해 알고 있다면, 쉽게 떠올릴 수 있었을 것이다. 다익스트라 알고리즘, 벨만-포드 알고리즘과 같은 것도 기본적으로 BFS를 기반으로 하는 알고리즘이다.

하지만, 이 문제의 경우에는 가중치가 없는 그래프이므로 저런 알고리즘까지 갈 것 없이, 그냥 BFS만 사용하여 해결할 수 있다. (벨만-포드를 사용할 경우 오히려 효율적인 측면에서 손해를 보게 된다.)

위 예시를 다시 가져와보자.

5 12

여기서 BFS를 진행해보자. 단, 이미 방문했던 노드는 재방문하지 않는다. 또, 큐에 노드를 저장할 때, 이동횟수도 함께 저장을 해준다.

1. 큐 [ ] : 이동 횟수 : 1
   • 5 → 6
   • 5 → 10
2. 큐 [4, 10] : 현재 노드 = 6 / 이동횟수 : 2
   • 6 → 5 : 5번 노드는 이미 방문했으므로, 큐에 추가하지 않는다.
   • 6 → 7
   • 6 → 12 (return 2)

벌써 최단 거리를 찾았다. 코드 상에서는 이때 이동 횟수를 리턴해주면 된다.

하지만 이게 최단 거리를 보장하는가에 의문이 들 수 있다. 이것에 대한 의문은 BFS가 노드를 방문하는 방법을 따라가면, BFS로 먼저 도달하는 경로가 최단거리를 보장한다는 것을 자연스럽게 알 수 있다.

코드로 구현하면 이렇게 된다.

private static int bfs(int start, int end) {  
    Queue<int[]> q = new LinkedList<>();  
    boolean[] visited = new boolean[100001];  
  
    int prev_pos = start;  
    int cnt = 0;  
    q.add(new int[]{prev_pos, cnt});  
  
    if(start >= end) {  
        return start - end;  
    }  
  
    while (true) {  
        int[] tmp = q.poll();  
        prev_pos = tmp[0];  
        visited[prev_pos] = true;  
  
        cnt = tmp[1] + 1;  
        int cur_pos;  
  
        int[] move = {prev_pos, 1, -1};  
        for (int i = 0; i < 3; i++) {  
            cur_pos = prev_pos + move[i];  
            // 가지치기
            if (cur_pos > 100000 || cur_pos < 0 || visited[cur_pos]) {  
                continue;  
            }  
  
            q.add(new int[]{cur_pos, cnt});  
  
            if(cur_pos == end) {  
                return cnt;  
            }  
        }  
    }
}

하지만 유의할 점이 몇 가지 있다.

Q. 수빈이의 위치가 100000을 초과할 수 있는가?

문제의 조건 상으로는 넘을 수는 있다. 시작할 때 주어지는 위치가 0 이상 100000이하인 것이지, 이동할 때는 상관이 없으니까.

• 50001 → 100002 → 100001 → 100000
• 50001 → 50000 → 100000

하지만 어느 경우라도 앞으로 갔다가 뒤로 빼는 것보다는 이렇게 가는 것이 더 빠르다. 또 100000을 초과하는 경우를 포함해버리면, 경우의 수가 너무 많아져 효율성이 떨어지는 문제가 발생한다.

Q. 수빈이의 위치가 음수가 될 수 있는가?

문제의 조건 상으로는 넘을 수 있다. 하지만, 음수로 갈 필요가 없다는 것을 명심하자. -1로 갈 수는 있지만, -1로 갔을 경우 최단 거리가 나올 수는 없다.

-1에서 순간이동을 하면 -2가 될 것이고, -1에서 다시 1칸 앞으로 이동하는 건 별 의미 없는 이동이 되니까.

이 당연한 것을 언급하는 이유는, 탐색 도중 수빈이의 위치가 음수가 되는 경우가 발생하기 때문이다. 이 경우에는 큐에 들어가지 않도록 가지치기를 해주어야 한다.

if (cur_pos > 100000 || cur_pos < 0 || visited[cur_pos]) {  
    continue;  
}

이 부분을 추가한 이유다. 효율성 때문도 있지만, visted 배열에서 Array Index Out of Bounds Exception 예외가 발생할 수 있기 때문이다.

결론. BFS로 가능하다.

 

DP?

DP는 충분히 가능성이 있어 보였다. 일단 범위 자체가 100,000으로 충분히 DP로 커버가 가능한 크기다.

수빈이의 위치부터 시작하여, 동생의 위치까지 각 위치마다 최소 이동 횟수를 기록하면서 나아가면 충분히 가능하지 않을까?

// end는 동생의 위치
// start은 수빈이의 시작 위치
int[] dp = new int[end+1]

int cnt = 0;  
for (int i = start; i >= 0; i--) {  
    dp[i] = cnt++;
}
cnt=0;  
for (int i = start; i <= end + 1; i++) {  
    dp[i] = cnt++;  
}

일단 이렇게 시작할 수 있겠다.

• 수빈이가 자신의 시작 위치까지 갈 수 있는 최단 거리는 가만히 아무것도 안 하는 것이므로 0인 것은 자명하다.
• 다른 위치는 무조건 한 칸씩 이동하여 움직였을 때로 초기화해준다. 이때, 최소 이동 거리보다 작은 값이 들어갈 수 없다는 것 또한 자명하다.

이제 천천히 생각해보자.

dp[17]로 이동할 수 있는 방법에는 무엇이 있을까?

16에서 한 칸 앞으로 이동, 18에서 한 칸 뒤로 이동. 17은 홀수이므로 이전 위치에서 순간이동으로 한 번에 도착할 수 있는 방법은 없다.

하지만, dp[9] → dp[18] → dp[17] 이렇게 두 번에 걸쳐 이동하는 것이 더 빠를 수도 있다. (이 경우가 18에서 한 칸 뒤로 이동하는 경우를 포함하고 있다는 것까지 생각하면 좋다.)

9 17로 입력이 들어왔을 경우를 생각해보자.

따라서, 의사코드로 정리하면

dp[17] = Math.min(dp[16]+1, dp[9]+2, dp[17]);

이렇게 된다.

dp[16]이라면?

15에서 한 칸 앞으로 이동, 17에서 한 칸 뒤로 이동, 8에서 순간이동.

dp[16] = min(dp[15]+1, dp[17]+1, dp[8]+1, dp[16]);

즉, 다음으로 이동해야할 위치가 짝수일 경우, 홀수일 경우를 분리하여 생각해야 한다.

이제 두 경우를 합쳐보자. 다음으로 이동해야 할 위치를 pos라고 했을 때, 최종 의사코드는 이렇게 될 것이다.

if(next_pos가 짝수 혹은 0이면)
    dp[pos] = min(dp[pos-1]+1, dp[pos+1]+1, dp[pos/2]+1, dp[pos])
else
    dp[pos] = min(dp[pos-1]+1, dp[(pos+1)/2]+1, dp[pos]);

이제 이대로 구현만 하면 된다.

private static int dp(int start, int end) {  
    if(start >= end) {  
        return start - end;  
    }  

    int[] dp = new int[end+2];  

    int cnt = 0;  
    for (int i = start; i >= 0; i--) {  
        dp[i] = cnt++;  
    }
    cnt=0;  
    for (int i = start; i <= end + 1; i++) {  
        dp[i] = cnt++;  
    }  

    for (int i = start + 1; i <= end; i++) {  
        if (i % 2 == 0) {  
            dp[i] = Math.min(dp[i], dp[i / 2] + 1);  
        } else {  
            dp[i] = Math.min(dp[i], dp[(i + 1) / 2] + 2);  
        }  

        dp[i] = Math.min(dp[i], dp[i - 1] + 1);  
    }  
    return dp[end];  
}

결론. DP로 가능.

 

---

 

코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.Arrays;  
import java.util.LinkedList;  
import java.util.Queue;  
import java.util.StringTokenizer;  

public class Main {  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer stk = new StringTokenizer(br.readLine());  

        int n, m;  
        n = Integer.parseInt(stk.nextToken());  
        m = Integer.parseInt(stk.nextToken());  

        // int answer = dp(n, m);
        int answer = bfs(n, m);
        System.out.println(answer);  
    }  

    private static int bfs(int start, int end) {  
        Queue<int[]> q = new LinkedList<>();  
        boolean[] visited = new boolean[100001];  

        int prev_pos = start;  
        int cnt = 0;  
        q.add(new int[]{prev_pos, cnt});  

        if(start >= end) {  
            return start - end;  
        }  

        while (true) {  
            int[] tmp = q.poll();  
            prev_pos = tmp[0];  
            visited[prev_pos] = true;  

            cnt = tmp[1] + 1;  
            int cur_pos;  

            int[] move = {prev_pos, 1, -1};  
            for (int i = 0; i < 3; i++) {  
                cur_pos = prev_pos + move[i];  

                // 가지치기  
                if (cur_pos > 100000 || cur_pos < 0 || visited[cur_pos]) {  
                    continue;  
                }
                q.add(new int[]{cur_pos, cnt});  

                if(cur_pos == end) {  
                    return cnt;  
                }  
            }  
        }  
    }  

    private static int dp(int start, int end) {  
        if(start >= end) {  
            return start - end;  
        }  

        int[] dp = new int[end+2];  

        int cnt = 0;  
        for (int i = start; i >= 0; i--) {  
            dp[i] = cnt++;  
        }  

        cnt=0;  
        for (int i = start; i <= end + 1; i++) {  
            dp[i] = cnt++;  
        }  

        for (int i = start + 1; i <= end; i++) {  
            if (i % 2 == 0) {  
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);  
            } else {  
                dp[i] = Math.min(dp[i], dp[(i + 1) / 2] + 2);  
            }  

            dp[i] = Math.min(dp[i], dp[i - 1] + 1);  
        }  
        return dp[end];  
    }  
}

 

---

 

성능 비교

• BFS : $O(n)$ : 실질적으로는 가지치기 코드 때문에 $O(end)$
  
• DP : $O(end)$ : 동생의 위치에 따라 반복 횟수가 달라지므로.
  

시간 복잡도는 똑같지만 DP가 더 빠른 것을 볼 수 있는데, 이것은 BFS에서는 큐를 사용하기 때문이다.

그렇다고는 해도 두 배 가까이 차이가 있을 줄은 몰랐다.

 

---

 

References

https://didu-story.tistory.com/441 : DP로 풀이하면서 참고했습니다. 제 글이 이해가 안 되었다면, 이 글을 참고하시는 것을 추천.