백준 2602번 돌다리 건너기 :: 마이구미

이 글은 백준 알고리즘 문제 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