[BOJ][C++] 백준 10164번: 격자상의 경로

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

 

문제

행의 수가 N이고 열의 수가 M인 격자의 각 칸에 1부터 N×M까지의 번호가 첫 행부터 시작하여 차례로 부여되어 있다. 격자의 어떤 칸은 ○ 표시가 되어 있다. (단, 1번 칸과 N × M번 칸은 ○ 표시가 되어 있지 않다. 또한, ○ 표시가 되어 있는 칸은 최대 한 개이다. 즉, ○ 표시가 된 칸이 없을 수도 있다.) 

행의 수가 3이고 열의 수가 5인 격자에서 각 칸에 번호가 1부터 차례대로 부여된 예가 아래에 있다. 이 격자에서는 8번 칸에 ○ 표시가 되어 있다.

 

격자의 1번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M번 칸으로 가고자 한다. 

• 조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다. (즉, 대각선 방향으로는 이동할 수 없다.)
• 조건 2: 격자에 ○로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 한다. 

위에서 보인 것과 같은 격자가 주어질 때, 로봇이 이동할 수 있는 서로 다른 경로의 두 가지 예가 아래에 있다.

• 1 → 2 → 3 → 8 → 9 → 10 → 15
• 1 → 2 → 3 → 8 → 13 → 14 → 15

격자에 관한 정보가 주어질 때 로봇이 앞에서 설명한 두 조건을 만족하면서 이동할 수 있는 서로 다른 경로가 총 몇 개나 되는지 찾는 프로그램을 작성하라. 

입력

입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다.

출력

주어진 격자의 정보를 이용하여 설명한 조건을 만족하는 서로 다른 경로의 수를 계산하여 출력해야 한다. 

 

풀이

K번 칸을 지나가는 경우의 수는

첫번째 칸에서 k번 칸까지 가는 경우의 수 * k번 칸에서 마지막 칸까지 가는 경우의 수

이 둘의 곱으로 나타낼 수 있다.

 

중학교 수학과정에 있는 최단 경로 찾기 문제 유형을 응용해서

고등학교 확통 경우의 수 단원에 나오는 유형이 있는데 딱 그거다

 

특정 칸까지 가는 경우의 수는 dp를 이용하여 구할 수 있다.

int ways(int n, int m) {
    vector<vector<int>>dp(n, vector<int>(m,1));
    
    for(int i=1; i<n; i++) {
        for(int j=1; j<m; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    
    return dp[n-1][m-1];
}

 

 

이제 k번 칸이 몇번째 줄 몇번째 칸인지 알아야한다

 

계산의 편의성을 위해 칸을 0부터 채운다고 가정하자

예를들어 n=3 m=5의 경우에 다음과 같이 될 것이다.

0	1	2	3	4
5	6	7	8	9
10	11	12	13	14

 

각 숫자를 m으로 나눈 몫과 나머지를 구해서 {몫, 나머지} 형태로 표현하면

0,0	0,1	0,2	0,3	0,4
1,0	1,1	1,2	1,3	1,4
2,0	2,1	2,2	2,3	2,4

 

몫은 행-1, 나머지는 열-1 을 나타내는 숫자라는걸 알 수 있다

 

즉, k번에 해당하는 좌표를 구할 수 있다

    k--;
    int x = k/m + 1;
    int y = k%n + 1;

 

코드

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>

using namespace std;

const int INF = 100001;

int ways(int n, int m) {
    vector<vector<int>>dp(n, vector<int>(m,1));
    
    for(int i=1; i<n; i++) {
        for(int j=1; j<m; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    
    return dp[n-1][m-1];
}

int solution(int n, int m, int k) {
    
    if(k==0) {
        return ways(n,m);
    }
    
    k--;
    int x = k/m + 1;
    int y = k%m + 1;
    
    int to_k = ways(x,y);
    int from_k = ways(n-x+1, m-y+1);

    return to_k * from_k;
}

int main() {
    int n,m,k;
    cin >> n >> m >> k;
    
    cout << solution(n,m,k);
    
    return 0;
}