[백준] 자바 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인 경우는 없다.

출력

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

---

테스트 케이스

 

입력 1

1 1 0

출력 1

1

 

입력 2

3 5 14

출력 2

10

 

입력 3

12 13 0

출력 3

1352078

---

접근

DFS를 이용하면 다른경로의 개수를 셀 수 있습니다.

EX

예시처럼 O가 있다면 반드시 지나가야 하므로 시작점에서 O까지 DFS, O에서 도착점까지 DFS하면 됩니다.

각각의 값을 얻어서 곱해주면 결과가 나오게 됩니다.

---

코드

import java.util.*;
import java.io.*;


public class Main {
	static int N,M,map[][];
	static int result = 0;
	public static void dfs(int x,int y, int ox, int oy) {
		if(x == ox && y == oy) {
			result++;
			return;
		}
		if(x > ox || y > oy) return;
		
		dfs(x+1,y,ox,oy);
		dfs(x,y+1,ox,oy);
	}
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		int temp = 0;
		int goalX = 0, goalY = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				map[i][j] = ++temp;
				if(temp == K) {
					goalX = i;
					goalY = j;
				}
			}
		}
		int res1 = 1;
		int res2 = 1;
		//O지점 있을때
 		if(K != 0) {
			dfs(0,0,goalX,goalY);
			res1 = result;
		}
 		result = 0;
		dfs(goalX,goalY,N-1,M-1);
		res2 = result;
		if(res1 == 0) res1 = 1;
		if(res2 == 0) res2 = 1;
		bw.write(String.valueOf(res1 * res2));
		bw.flush();
		br.close();
		bw.close();
	}

}

---

주의

K=0이면 O없음!