• 백준 2602번 돌다리 건너기 :: 마이구미
    알고리즘 풀이/동적계획법 2019. 11. 10. 23:18
    반응형
    이 글은 백준 알고리즘 문제 2063번 "돌다리 건너기" 를 풀이한다.
    정올 고등부 문제이자, 동적계획법(DP) 문제이다.
    문제 링크 - https://www.acmicpc.net/problem/2602

     

    절대반지를 얻기 위하여 반지원정대가 출발한다. 원정대가 지나가야할 다리는 두 개의 인접한 돌다리로 구성되어 있다. 하나는 <악마의 돌다리>이고 다른 하나는 <천사의 돌다리>이다.

    아래 그림 1은 길이가 6인 다리의 한 가지 모습을 보여준다. 그림에서 위의 가로줄은 <악마의 돌다리>를 표시하는 것이고, 아래의 가로줄은 <천사의 돌다리>를 표시한다. 두 돌다리의 길이는 항상 동일하며, 각 칸의 문자는 해당 돌에 새겨진 문자를 나타낸다. 두 다리에 새겨진 각 문자는 {R, I, N, G, S} 중 하나이다.

    출발 R I N G S R 도착
    G R G G N S

    반지원정대가 소유하고 있는 마법의 두루마리에 <악마의 돌다리>와 <천사의 돌다리>를 건너갈 때 반드시 순서대로 밟고 지나가야할 문자들이 적혀있다. 이 순서대로 지나가지 않으면 돌다리는 무너져 반지원정대는 화산 속으로 떨어지게 된다.

    다리를 건널 때 다음의 제한 조건을 모두 만족하면서 건너야 한다.

    1. 왼쪽(출발지역)에서 오른쪽(도착지역)으로 다리를 지나가야 하며, 반드시 마법의 두루마리에 적힌 문자열의 순서대로 모두 밟고 지나가야 한다.
    2. 반드시 <악마의 돌다리>와 <천사의 돌다리>를 번갈아가면서 돌을 밟아야 한다. 단, 출발은 어떤 돌다리에서 시작해도 된다.
    3. 반드시 한 칸 이상 오른쪽으로 전진해야하며, 건너뛰는 칸의 수에는 상관이 없다. 만일 돌다리의 모양이 그림 1과 같고 두루마리의 문자열이 "RGS"라면 돌다리를 건너갈 수 있는 경우는 다음의 3가지 뿐이다. (아래 그림에서 빨간색 문자는 밟고 지나가는 돌다리를 나타낸다.)

     


     

    문제는 두 개의 돌다리가 존재하고, 조건을 충족시키면서 다리를 건널 수 있는 모든 경우의 수를 요구한다.

    조건은 다음과 같다.

     

    • 입력된 문자열을 모두 밟고 지나가야한다.
    • 두 개의 돌다리를 번갈아가면서 지나가야한다.
    • 반드시 한 칸 이상 전진하면서 지나가야한다.

     

    처음에 본인은 주어지는 입력 길이가 크지 않았기 때문에 완전탐색으로 접근했다.

    쉽게 말해서, 모든 경우를 다 살펴보면 된다.

     

    public static void move(int f, int c, int r) {
        if (f == find.length) {
            ans++;
            return;
        }
    
        if (r == 0) {
            for (int i = c; i < devil.length; i++) {
                if (find[f] == devil[i]) {
                    move(i + 1, f + 1, 1); // 천사의 돌다리로 변경
                }
            }			
        } else {
            for (int i = c; i < angel.length; i++) {
                if (find[f] == angel[i]) {
                    move(i + 1, f + 1, 0); // 악마의 돌다리로 변경
                }
            }
        }
    }

     

    위 코드처럼 재귀적으로 한칸씩 전진하면서, 모든 경우에 대해 탐색하였다.

    문제는 정답이였지만, 재채점으로 인해 시간초과가 났다.

    작은 입력값이였지만, 결국 최악의 경우에는 시간초과를 초래할 수 밖에 없었다.

     

    다시 문제를 접근하면서, 지금 코드를 그대로 사용하면서 해결할 수 있어보였다.

    그 이유는 완전 탐색 과정에서 재사용할 수 있는 값들이 존재하기 때문이다.

    재사용할 수 있는 값은 예제를 통해 알아보자.

    예제는 "RGS" 순서대로 밟아야하는 경우라고 가정한다.

     

     

    위 그림은 의식의 흐름대로 RGS 를 찾았을 때의 경우이다.

    첫번째는 악마의 돌다리 R 을 밟고, 천사의 돌다리 G 를 밟은 후, 악마의 돌다리 6번째 S 를 밟는다.

    두번째는 악마의 돌다리 R 을 밟고, 천사의 돌다리 G 를 밟은 후, 악마의 돌다리 7번째 S 를 밟는다.

    세번째는 악마의 돌다리 R 을 밟고, 천사의 돌다리 G 를 밟은 후, 악마의 돌다리 8번째 S 를 밟는다.

     

    그 이후 경우는 악마의 돌다리 G 를 밟은고, 천사의 돌다리에서 4번째 G 를 밟을 것이다.

     

     

    그리고는 천사의 다리 G 위치만 다른 상태로, 이전과 동일하게 악마의 돌다리 S 를 밟을 수 있다.

     

     

    위 행위가 끝나면, 또다시 천사의 돌다리 G 를 5번째로 옮긴 후, 똑같은 경우를 반복할 것이다.

    결국 우리는 똑같은 탐색을 하고 있다는 것을 알 수 있다.

    1, 2, 3번째에서 한 행위를 재사용하기 위해 다음과 같은 DP 배열을 만들어낼 수 있다.

     

    dp[현재 밟은 문자][찾는 문자][어떤 돌다리]
    ex) G 을 밟고 찾는 문자가 S 이면서, 현재 악마의 돌다리인 경우

     

    간단한 DP 방식을 추가한 방식으로, 처음 작성한 완전 탐색 코드에 넣으면 된다.

     

    public static int move(int c, int f, int r) {
        if (f == find.length) {
            return 1;
        }
    
        if (dp[c][f][r] > -1) {
            return dp[c][f][r];
        }
    
        int total = 0;
        if (r == 0) {
            for (int i = c; i < devil.length; i++) {
                if (find[f] == devil[i]) {
                    total += move(i + 1, f + 1, 1);
                }
            }
        } else {
            for (int i = c; i < angel.length; i++) {
                if (find[f] == angel[i]) {
                    total += move(i + 1, f + 1, 0);
                }
            }
        }
        return dp[c][f][r] = total;
    }

     

    Github - https://github.com/hotehrud/acmicpc/blob/master/KOI/2004/2602.java

    반응형

    댓글 0

Designed by Tistory.