백준 15924 욱제는 사과팬이야!!

https://www.acmicpc.net/problem/15924

15924번: 욱제는 사과팬이야!!

---

문제

욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물

을 전달해주려고 한다. 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다.

구사과가 있는 곳은 N×M 크기의 직사각형 지도로 나타낼 수 있으며, 1×1크기의 정사각형으로 나누어져 있다. 구사과의 위치는 (i, j)로 나타낼 수 있으며, (i, j)는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸을 의미한다.

지도의 각 칸에는 E, S, B중의 한 문자가 쓰여져 있는데, 구사과는 이 문자를 이용해서 이동한다. 구사과의 위치가 (i, j)인 경우에 E가 쓰여져 있는 칸에 서 있었다면 (i, j+1)로, S의 경우에는 (i+1, j)로, B의 경우에는 (i, j+1) 또는 (i+1, j)로 순간이동한다. 구사과는 지치지 않기 때문에, 계속해서 이동한다.

욱제는 구사과의 위치를 모르지만, 구사과가 이동을 시작하는 위치와 관계없이 최종 목적지는 항상 (N, M)이라는 사실을 알고 있다. 욱제는 (N, M)에 선물을 배치해서 구사과가 항상 선물을 가져갈 수 있게 할 작정이다. 구사과가 선물을 가져가는 경로의 수를 구하는 프로그램을 작성하시오. 선물이 놓여진 칸에 구사과가 이동하면, 구사과는 항상 선물을 가져간다.

---

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 3,000)

둘째 줄부터 N개의 줄에는 구사과가 있는 곳의 지도가 주어진다. (N, M)에는 도착지임을 뜻하는 X가 주어진다.

지도에 쓰여 있는 대로 이동했을 때, 지도를 벗어나는 경우는 없다.

---

출력

첫째 줄에 구사과가 선물을 가져가는 경로의 수를 출력한다. 경로가 너무 많아질 수 있으므로 1,000,000,009 (109 + 9)로 나눈 나머지를 출력한다.

---

저도 구사과님의 팬입니다ㅏ..

문제에서 지도에 문자 E,S,B가 적혀있고 E는 자신의 위치에서  (i, j+1) 즉, 오른쪽으로 이동할 수 있습니다.

S는 (i+1, j), 위로 이동할 수 있고, B는  (i, j+1) 또는 (i+1, j)로 즉 E와 S모두 가능합니다.

중간에 멈추는 경우는 존재하지 않습니다.

 

그리고 계산 과정마다 1,000,000,009 로 나눠줘야 합니다.

일단 먼저 지도를 입력받았고,  2차원 DP배열을 모두 1로 초기화해주었습니다.

 

   cin >> n >> m;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            cin >> arr[i][j];
            dp[i][j] = 1;
        }
    }

그 후 ,bool 변수 한 개 (기본값으로 FALSE)를 선언하였는데, 이것은 지도의 끝에 도달하면  TRUE로 바뀌고 탐색이 끝납니다.

 

  if(i == n-1 && j == m-1){ //지도의 끝
                 is_end = true;
                 break;
             }

현재 지도에 적혀 있는 값이 B인경우)

 

B일 떄는 현재 위치가 (i,j)라면 (i,j+1),(i+1,j)모든 방향으로 이동이 가능합니다.

j+1이 m보다 작다면, 즉 지도를 벗어나지 않는다면 dp[i][j+1]의 값을 dp[i][j]와 더해줍니다. (계산과정마다 mod연산 )

 

  if(j+1 < m){
                    dp[i][j+1] = dp[i][j+1] % MOD + dp[i][j] % MOD;
                }

 

마찬가지로 i+1이 n보다 작다면 dp[i+1][j]의 값과 dp[i][j]를 더해 줍니다. (계산 과정마다 mod연산 )

 if(i+1 < n){
                    dp[i+1][j] = dp[i+1][j]%MOD + dp[i][j]%MOD;
                }

 

현재 지도에 적혀 있는 값이 E인 경우)

 

E는 자신의 위치에서  (i, j+1) 즉, 오른쪽으로 이동할 수 있습니다.

j+1이 m보다 작은 경우에 한해서 dp[i][j+1]의 값을 dp[i][j]와 합해서 갱신해 줍니다.

 

마지막으로 지도에 적혀 있는 값이 S인 경우입니다)

 

(i+1, j)로 이동 가능하므로, i+1이 n보다 작을떄 DP[i+1][j]를 갱신해주면 됩니다.

---

전체 코드 입니다->

#include <iostream>
#define MOD 1000000009
using namespace std;
typedef long long ll;
 
char arr[3001][3001];
int n,m;
ll dp[3001][3001];
 
int main(void){
    cin >> n >> m;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            cin >> arr[i][j];
            dp[i][j] = 1;
        }
    }
 
    dp[0][0] = 1;
    bool is_end = false;
 
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
             if(i == n-1 && j == m-1){
                 is_end = true;
                 break;
             }
            if(arr[i][j] == 'B'){
                if(i+1 < n){
                    dp[i+1][j] = dp[i+1][j]%MOD + dp[i][j]%MOD;
                }
                if(j+1 < m){
                    dp[i][j+1] = dp[i][j+1] % MOD + dp[i][j] % MOD;
                }
            }
            else if(arr[i][j] == 'E'){
                if(j+1 < m){
                    dp[i][j+1] = dp[i][j+1] % MOD + dp[i][j] % MOD;
                }
            }
            else if(arr[i][j] == 'S'){
                if(i+1 < n){
                    dp[i+1][j] = dp[i+1][j] % MOD + dp[i][j] % MOD;
                }
            }
        }
        if(is_end == true){
            break;
        }
 
    }
    cout << dp[n-1][m-1] % MOD;
}