[Java] 백준 / 격자상의 경로 / 10164번

[Java] 백준 / 격자상의 경로 / 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인 경우는 없다.

7 11 76

출력

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

5005

접근 방식

1. K 위치의 행열 인덱스를 저장한다 ( 초기화 0,0 )
2. 행 N, 열 M 크기의 dp 배열을 만들고 행열 둘중 하나라도 인덱스가 0이면 값을 1, 아니면 [행 -1][열] 값과 [행][열 -1] 값을 더해 자신에게 넣는다
3. K를 거쳐가면 0,0 에서 K 위치까지의 경우의 수와 K위치에서 끝까지의 경우의 수를 곱하면 되기 때문에 dp[kI][kJ]값과 dp[N-kI -1][M-kJ-1] 값을 곱한다
4. K가 0이라도 dp[0][0] * dp[N-1][M-1] 을 계산하게 된다

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_S1_10164 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int matrix[][] = new int[N][M];
		
		int kI = 0;
		int kJ = 0;
		int cnt = 1;
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(i ==0 || j == 0) matrix[i][j] = 1;
				else {
					matrix[i][j] = matrix[i-1][j] + matrix[i][j-1];
				}
				
				if(cnt == K) {
					kI = i;
					kJ = j;
				}
				cnt++;
			}
		}
		
		System.out.println(matrix[kI][kJ] * matrix[N-kI-1][M-kJ-1]);
		
	}

}