[BOJ] 백준 2602 : 돌다리 건너기 (java)

🧪 2602 돌다리 건너기

---

난이도 : 🌟 골드 4
유형 : 동적 프로그래밍

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가지 뿐이다. (아래 그림에서 빨간색 문자는 밟고 지나가는 돌다리를 나타낸다.)

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

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

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

아래의 세 방법은 실패한 방법이다.

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

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

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

왜냐하면 첫 번째는 문자열 "RGS"를 모두 밟고 지나가야 하는 조건 1)을 만족하지 않으며, 두 번째는 번갈아가면서 돌을 밟아야 하는 조건 2)를, 세 번째는 앞으로 전진을 하여야하는 조건 3)을 만족하지 않기 때문이다.

마법의 두루마리에 적힌 문자열과 두 다리의 돌에 새겨진 문자열이 주어졌을 때, 돌다리를 통과할 수 있는 모든 가능한 방법의 수를 계산하는 프로그램을 작성하시오. 예를 들어, 그림 1의 경우는 통과하는 방법이 3가지가 있으므로 3을 출력해야 한다.

 

 

입력

 

첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 <악마의 돌다리>와 <천사의 돌다리>를 나타내는 같은 길이의 문자열이 주어진다. 그 길이는 1 이상, 100 이하이다.

 

출력

 

마법의 두루마리에 적힌 문자열의 순서대로 다리를 건너갈 수 있는 방법의 수를 출력한다. 그러한 방법이 없으면 0을 출력한다.

모든 테스트 데이터에 대한 출력결과는 231-1 이하이다.

 

🧐 핵심 로직 

---

1) 완전탐색을 사용하는 경우 시간이 초과된다. 그렇기 때문에 DP를 사용한다.

 

2) dp의 각 행의 의미는 dp[현재 밟은 문자][찾는 문자][어떤 돌다리]

    2 - a) ex) G 을 밟고 찾는 문자가 S 이면서, 현재 악마의 돌다리인 경우가 이전에 있었다면 같은 결과가 나오도록 dp를 만들어준다.

 

3) 그 후, 재귀를 반복해서 결과값을 구한 후 출력한다.

 

💻 최종 코드 (128 ms)

---

import java.io.*;
import java.util.*;

public class Main {

    static String target, devil, angel;
    static int[][][] dp;
    public static void main(String[] args) throws IOException {

        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));

        target = br.readLine();
        devil = br.readLine();
        angel = br.readLine();

        int bridgeLen = devil.length();
        dp = new int[target.length() + 1][bridgeLen + 1][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < bridgeLen; j++) {
                for (int k = 0; k < target.length(); k++) {
                    dp[k][j][i] = -1;
                }
            }
        }

        int dev_start = crossBridge(0,0,0);
        int ang_start = crossBridge(0,0,1);

        System.out.println(dev_start + ang_start);

        br.close();
    }

    private static int crossBridge(int idx, int curStone, int turn) {

        if (idx == target.length()) return 1;
        if (dp[idx][curStone][turn] != -1) return dp[idx][curStone][turn];

        int res = 0;
        if (turn == 0) {
            for (int i = curStone; i < devil.length(); i++) {
                if (devil.charAt(i) == target.charAt(idx)) {
                    res += crossBridge(idx + 1, i + 1, 1);
                }
            }
        } else {
            for (int i = curStone; i < angel.length(); i++) {
                if (angel.charAt(i) == target.charAt(idx)) {
                    res += crossBridge(idx + 1, i + 1, 0);
                }
            }
        }

        return dp[idx][curStone][turn] = res;
    }
}

💻 시간 초과 코드

---

import java.io.*;
import java.util.*;

public class Main {

    static int res;
    static String target, devil, angel;
    public static void main(String[] args) throws IOException {

        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));

        target = br.readLine();
        devil = br.readLine();
        angel = br.readLine();

        crossDevil(0, 0);
        crossAngel(0, 0);

        System.out.println(res);

        br.close();
    }

    private static void crossDevil(int idx, int curStone) {

        if (idx == target.length()) {
            res++;
            return;
        }

        for (int i = curStone; i < devil.length(); i++) {
            if (devil.charAt(i) == target.charAt(idx)) {
                crossAngel(idx + 1, i + 1);
            }
        }
    }

    private static void crossAngel(int idx, int curStone) {

        if (idx == target.length()) {
            res++;
            return;
        }

        for (int i = curStone; i < angel.length(); i++) {
            if (angel.charAt(i) == target.charAt(idx)) {
                crossDevil(idx + 1, i + 1);
            }
        }
    }
}