[BOJ] 백준 2602번 돌다리 건너기 (Java)

#2602 돌다리 건너기

난이도 : 골드 4

유형 : DP

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을 출력한다.

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

 

문제 풀이 

조건을 잘 정리하여 DP를 통해 풀이하면 가볍게 풀리는 문제이다. 나는 재귀 호출 방식으로 설계해서 풀이를 했다.

 

📚 조건

   ∙ 건너야하는 문자열(마법 두루마리)의 길이 최소 1, 최대 20

   ∙ 다리 종류 2개로 악마, 천사

   ∙ 다리 길이 len (1<= len <=100)

   ∙ 다리 건너는 조건

       1) 왼쪽에서 시작 > 오른쪽으로 도착, 주어진 문자열을 모두 밞고 지나가야 한다.

       2) 악마, 천사를 번갈아가면서 돌을 밞아야 한다. (출발은 어떤 돌다리 상관없음) → 두 가지 케이스로 모두 실행해봐야 함

       3) 한 칸 이상 오른쪽으로 전진, 건너뛰는 칸의 수 상관없음

 

      → 다리 건너는 경우의 수를 구해서 출력한다.

 

 

풀이 코드 

주어진 문자열(str)을 들고 천사와 악마다리를 조회해가면서 일치하는 문자열이 있을 때 다음 단계로 넘어가게 해주면 된다. 그리고 출발 다리가 정해지지 않았으므로 천사, 악마 먼저 출발하는 경우 두가지를 모두 구해서 더해줘야한다.

import java.io.*;

public class Main {

	static String[] str,dev,ang;
	static int[][][] dp;
	static int len;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		str = br.readLine().split("");
		dev = br.readLine().split("");
		ang = br.readLine().split("");
		len = dev.length;
		dp = new int[str.length+1][len+1][2];
		for(int i=0; i<2; i++) {
			for(int j=0; j<len; j++) {
				for(int k=0; k<str.length; k++) {
					dp[k][j][i] = -1;
				}
			}
		}
		int dev_start = dfs(0,0,0);
		int ang_start = dfs(0,0,1);
		System.out.println(dev_start+ ang_start);
	}
	
	// pos : 현재 건너는 str위치
	// idx : 천사/악마 dev, ang 위치
	// trun : 1== 악마, 0== 천사
	static int dfs(int pos, int idx, int turn){
		if(pos == str.length) {
			return 1;
		}
		if(dp[pos][idx][turn] != -1) return dp[pos][idx][turn];
		int count =0;
		if(turn==0) { // 악마 
			for(int i=idx; i<len; i++) {
				if(str[pos].equals(dev[i])) {
					count += dfs(pos+1, i+1, 1);
				}
			}
		}
		else { // 천사 
			for(int i=idx; i<len; i++) {
				if(str[pos].equals(ang[i])) {
					count += dfs(pos+1, i+1, 0);
				}
			}
		}
		return dp[pos][idx][turn] = count;
	}
}