Bridge

1. 문제

절대반지를 얻기 위하여 반지원정대가 출발한다.

원정대가 지나가야할 다리는 두 개의 인접한 돌다리로 구성되어 있다.

하나는 <악마의 돌다리>이고, 다른 하나는 <천사의 돌다리> 이다.

 

아래 [그림 1]은 길이가 6인 다리의 한 가지 모습을 보여준다.

그림에서 위의 가로줄은 <악마의 돌다리>를 표시하는 것이고,

아래의 가로줄은 <천사의 돌다리>를 표시한다.

두 돌다리의 길이는 항상 동일하며, 각 칸의 문자는 해당 돌에 새겨진 문자를 나타낸다.

두 다리에 새겨진 각 문자는 { R, I, N, G, S } 중 하나이다.

[그림 1]  

반지원정대가 소유하고 있는 마법의 두루마리에는

<악마의 돌다리>와 <천사의 돌다리>를 건너갈 때

반드시 순서대로 밟고 지나가야할 문자들이 적혀있다.

이 순서대로 지나가지 않으면 돌다리는 무너져, 반지원정대는 화산 속으로 떨어지게 된다.

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

 

[제한조건]

​1.     왼쪽(출발지역)에서 오른쪽(도착지역)으로 다리를 지나가야 하며,    

        ​​반드시 마법의 두루마리에 적힌 문자열의 순서대로 모두 밟고 지나가야 한다.

 

2.     반드시 <악마의 돌다리>와 <천사의 돌다리>를 번갈아가면서 돌을 밟아야 한다.

        단, 출발은 어떤 돌다리에서 시작해도 된다.

 

3.     반드시 한 칸 이상 오른쪽으로 전진해야하며, 건너뛰는 칸의 수에는 상관이 없다.  

       ​만일, 돌다리의 모양이 위의 [그림 1]과 같고,

       두루마리의 문자열이 "RGS"라면 돌다리를 건너갈 수 있는 경우는 다음의 3가지 뿐이다.

       (아래 그림에서 큰 문자는 밟고 지나가는 돌다리를 나타낸다.) 

 

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

왜나하면, 첫 번째 문자열 "RGS"를 모두 밟고 지나가야 하는 조건 (1)을 만족하지 않으며,

두 번째는 번갈아가면서 돌을 밟아야 하는 조건 (2)를, 세 번째는 앞으로 전진을 하여야하는

조건 (3)을 만족하지 않기 때문이다.

 

마법의 두루마리에 적힌 문자열과 두 다리의 돌에 새겨진 문자열이 주어졌을 때,

돌다리를 통과할 수 있는 모든 가능한 방법의 수를 계산하는 프로그램을 작성하시오.

예를 들어, [ 그림 1 ]의 경우는 통과하는 방법이 3가지가 있으므로,

3을 출력해야 한다.

실행시간은 1초를 초과할 수 없다.

 

입력형식

첫째 줄에는 마법의 두루마리에 적힌 문자열 {R,I,N,G,S 로만 구성된} 이 주어진다.

이 문자열의 길이는 최소 2, 최대 20이다.

그 다음 두 줄에는 각 각 <악마의 돌다리>와 <천사의 돌다리>를 나타내는 같은 길이의 문자열이 주어진다.

그 길이는 5이상, 100이하 이다.

 

출력형식

출력 파일에 마법의 두루마리에 적힌 문자열의 순서대로

다리를 건너갈 수 있는 방법의 수를 출력한다.

그러한 방법이 없으면 0을 출력한다.

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

 

입출력 예 

입력

RGS

RINGSR

GRGGNS

​ 

출력

3

 

2. 문제 분석

위의 문제는 선형탐색으로 해결할 수 있는 문제이다.

위의 용어를 간단히 하기 위해서 아래와 같이 정의하자.

두루마리에 적힌 문자열을 Roll이라 칭하겠다.

그리고,  <악마의 돌다리>와 <천사의 돌다리> 를 하나의 2차원배열로 정의를 하고

이름을  StoneBridge라 칭하겠다.

 

문자의 간략화를 위해서, 아래와 같이 문자열들을 고정 시키자.

Roll은 "RGS" 라고 고정시키고,

StoneBridge의 0번째 행을 천사의 돌다리로, 1번째 행을 악마의 돌다리로 두자.

천사의 돌다리의 문자열을 "RINGSR" 로, 악마의 돌다리의 문자열을 "GRGGNS"라 한다.

 

위를 말로만 설명해서는 쉽게 와닿지 않을 테니, 배열로 정리해보면 아래와 같다.

위의 StoneBridge배열의 0번째 행을 쭉 읽으면 "RINGSR"로 천사의 돌다리를 의미.

그리고, 1번째 행을 쭉 읽으면 "GRGGNS"로 악마의 돌다리를 의미한다.

그리고, 여기서 한가지 중요한 것은 Roll배열을 탐색할 때,

R->G->S 순으로 탐색을 하지 않고, 그 반대방향으로 탐색을 시작 할 것이다.

즉, S->G->R 순으로 탐색을 할 것이다.

 

그리고, 이 문제를 해결 하기 위해서는 한 가지 더 필요한 변수가 있다.

즉, 기록을 위한 배열이 하나 더 필요하다.

이 배열의 이름을 DynamicTable이라 하며, 아래와 같다.

그런데 궁금한 것이 있을 것이다.

왜 하필, DynamicTable은 3 X 2 공간으로 이루어진 배열인지를.

그 이유는 두 개의 행이 필요한 이유는 천사와 악마 라는 개체가 2개이므로,

그리고 열의 개수가 3개인 이유는 Roll배열의 길이만큼 필요해서 이다. .

즉, Roll 배열의 "RGB"에 따른 각 문자에 대한 값을 매기기 위해서 이다.

그러나, 위에서 열의 개수가 하나 더 필요하다.

아래를 보자.

위의 배열에서 반드시 DynamicTable[0][0] 과 DynamicTable[1][0] 은 1로 세팅이 되있어야

한다. 왜 1로 세팅을 해야 하는지는 밑에서 설명하겠다.

간략히 설명하면, 우리가 "RGS" 문자열을 찾아서 S가 나오면 무사히 한 가지 경우가

생성이 된다.

그런데, 여기서 항상 생각해야 할 것은 RGS가 순서대로 탐색이 끝마쳐야 한 가지 경우로

생성이 된다.

이 시작점으로 잡힐 R은 천사 혹은 악마에게서는 반드시 있어야 한다.

그렇기 때문에 열의 0번째 인덱스를 1로 세팅을 한 것이다.

밑의 그림과 연동해서 보도록 하자.

우리가 탐색을 해야할 배열은  StoneBridge, Roll배열이다.

 

나머지 공간은 0으로 초기화가 되어 있어야 한다.

한번 더 자세히 보면, 아래와 같다.

결과론적으로 먼저 말하면

문제 풀이과정이 다 끝나면 DynamicTable에 값이 어떻게 되는지부터 보자.

그리고 최종 결과 값은 아래와 같이 얻는다.

 

탐색을 진행해보도록 하자.

위의 그림과 같이 Roll배열의 맨 미자막 인덱스의 값 S와 StoneBridge배열의 첫 번째 인덱스에

같은 문자가 하나도 존재하지 않는다.

이 경우에는 Pass하고 다음조건으로 넘어 간다.

위의 그림에서 천사쪽에는 G가 없다. 천사쪽에서는 패스한다.

그런데, 악마쪽에는 G가 있다.

이 의미가 무엇을 의미하냐면, 악마 쪽에 G가 있기 때문에, 천사쪽에서는 반드시 S가 존재해야

한다. 그 이유는 R->G->S 순으로 거쳐가야 하기 때문이다.

즉, 악마쪽 다리에서 G를 밟았다면, 천사쪽 돌다리에서 S를 밟아야 한다는 조건이 있으므로.

DynamicTable 배열을 보자.

위에서와 같이 악마쪽에서 G가 있으면, 천사쪽의 S가 있는 인덱스의 공간에

누적합으로 더한다.

그리고, 다음 탐색을 진행하자.

위에서 천사쪽 인덱스에 R이 있다.

천사쪽에 R이 있으면, 악마쪽에는 G가 있어야 한다.

악마쪽의 인덱스에는 누적합이 들어가야 하니까,

아래처럼 된다.

그리고 Roll배열을 한 번 탐색했으므로, StoneBridge배열의 인덱스를 옮겨줄 차례이다.

아래 그림을 보자.

위에서 S문자가 스톤브릿지배열에 존재하지 않는다.

다음조건으로 넘어간다.

G도 없다. 다음조건으로 넘어간다.

천사쪽에서는 R이 없다. 그런데, 악마쪽에서는 R이 존재한다.

악마쪽에서 R이 있다는 의미는, 다음에 밟아야 할 돌은 천사쪽 돌다리의 G이다.

그러므로,

그리고, 누적합을 해야 하니까,

그리고 다음 탐색으로 넘어가자. Roll배열을 다 검사했으니,

스톤브릿지 배열의 위치를 옮겨주자.

S가 없다. 다음 조건으로 넘어가자.

천사에는 G가 없다. Pass하며, 악마쪽에는 G가 존재한다.

악마쪽에 G가 있어야 한다는 것은, 천사쪽 돌다리에 S가 존재해야하다는 의미이므로,

아래와 같다.

그리고 누적합을 하면,

그리고, 다음 조건으로 넘어가자.

두 돌다리 모두에 R이 없으므로, 넘어간다.

그리고 Roll배열을 모두 탐색 했으니, 스톤브릿지 배열의 인덱스를 옮겨준다.

두 돌다리 모두에 S이 없으므로, 넘어간다.

천사와 악마쪽 돌다리 모두에 G가 들어 있다. 천사쪽부터 처리하자.

천사에 G가 있다. 그러면, 악마쪽 돌다리에 S가 있어야 하므로,

그리고, 누적합은 아래와 같다.

그리고, 악마쪽 돌다리에도 G가 있으므로, 천사쪽 돌다리에 S가 있어야 하므로,

다시,

그리고, 누적합은 아래와 같다.

그리고, 다음 조건으로 넘어가자.

두 돌다리에 R이 없으므로, 넘어가고, Roll배열을 탐색을 마쳤으니,

스톤브릿지 배열의 인덱스를 옮겨준다.

천사쪽에 S가 존재한다. 그런데 여기서 천사쪽에서 S 돌을 밟으면,

RGS탐색이 끝나서, 악마의 돌다리를 밟지 않아도 된다.

즉, 다음과 같이 된다.

그리고, 누적합은,

다음 탐색으로 넘어가자.

두 돌다리 모두에 G는 없다. 다음 조건으로 건너가자.

 

두 돌다리 모두에 R은 없다. 그리고, Roll배열을 모두 탐색했으니,

스톤브릿지 배열의 인덱스의 위치를 옮겨주자.

천사의 위치에 S가 없으나, 악마의 돌다리에 S가 있다.

그리고, 악마쪽 돌다리에 S를 밟았다는 것은, 더 이상 천사쪽 돌다리를 밟지 않아도 된다.

즉, RGS순으로 돌을 다 밟았다는 의미 이다.

즉, 아래와 같다.

누적합을 구하면,

그리고, 다음 탐색으로 넘어가자.

G는 두 돌다리 모두에 없다.

다음조건으로 넘어가자.

천사쪽 돌다리에 R이 있다.

그러면, 다음에 밟아야 할 돌은 악마쪽 돌다리의 G이다.

그러면, 아래와 같다.

누적합을 구하면,

이로써 모든 탐색이 끝이다.

경우의 수를 구하면 된다.

 

위에서와 같이 경우의 수는 맨 마지막 열의 값을 더해주면 된다.

2 + 1 = 3 이므로, 답은 3이다.

 

3. 구현

프로그램 실행결과

 

4. 소스 파일

main.c

0.00MB