[백준] 10164번. 격자상의 경로
1. 문제
행의 수가 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
격자에 관한 정보가 주어질 때 로봇이 앞에서 설명한 두 조건을 만족하면서 이동할 수 있는 서로 다른 경로가 총 몇 개나 되는지 찾는 프로그램을 작성하라.
2. 입력
입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다.
3. 출력
주어진 격자의 정보를 이용하여 설명한 조건을 만족하는 서로 다른 경로의 수를 계산하여 출력해야 한다.
4. 풀이
- 등굣길 문제 변형 버전
row, col이 주어질 때 경로 경우의 수를 리턴하는 함수를 만들었다.- 특정점을 꼭 지나야 한다는 말은
(시작점에서 특정점까지 경로)X(특정점에서 목적지까지 경로)를 구하면 된다. 꼭 지나야 하는 점이 최대 하나라서 수월하다. - 특정점 구하는 식은
m * i + j + 1 == k, 문제에서는(1, 1)에서 시작했지만 인덱스가 별로 필요없어서(0, 0)기준으로 식을 세웠다. - K가 0이면 답은
getRoute(n, m)이고 K가 0이 아니면answer = getRoute(i+1, j+1) X getRoute(n-i, m-j)
5. 처음 코드와 달라진 점
- 경로 구하기에서 테두리를 1로 초기화 해야 하는데 i로 했다가 수정했다.
- K와 인덱스의 관계식을 잘못 써서 수정했다.
m * (i+1) + j + 1 == k=>m * i + j + 1 == k
6. 코드
#include <iostream>
#include <algorithm>
using namespace std;
int getRoute(int row, int col) {
int arr[15][15];
for (int i = 0; i < col; i++) arr[0][i] = 1;
for (int i = 0; i < row; i++) arr[i][0] = 1;
for (int i = 1; i < row; i++){
for (int j = 1; j < col; j++) {
arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
}
}
return arr[row - 1][col - 1];
}
int main() {
int n, m, k;
cin >> n >> m >> k;
int answer;
if (k == 0) answer = getRoute(n, m);
else {
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (m * i + j + 1 == k) {
answer = getRoute(i + 1, j + 1) * getRoute(n - i, m - j);
break;
}
}
}
}
cout << answer;
}