문제 정리

---

R x C 맵에서
(r, 1)에서 (1, c)로 K칸만에 가는 방법의 수를 구하는 것이 목표이다
단, T로 표시된 부분은 지나갈 수 없고 경로중 같은 칸은 1번만 갈 수 있다

입력

---

R C K
맵 정보

출력

---

K칸으로 갈 수 있는 방법의 수

idea 정리

---

특정 경로를 알아봐야하니 dfs를 활용해야한다
한가지 방법에서 같은 칸을 방문하면 안되니 방문 처리를 해 줘야한다
그리고 이 방문 처리는 다른 경로에서는 갈 수 있어야 하므로 현재 경로의 dfs를 돌고 나면 방문 처리를 해제해 줘야한다
순열에서 selected를 체크해줬다가 풀어주는거랑 같은 의미이다
그리고 T에는 가지 않도록 체크만 해주면 된다

알고리즘 정리

---

1. (R, 1)에서 시작해 dfs를 돈다
2. 다음 칸으로 들어가기 전에 방문 처리를 해준다
   2-1. 방문이 끝나고 다시 돌아왔을땐 다른 경로를 위해 방문 처리를 해제해준다
3. (1, C)에 도착한 경우 depth가 K인 경우만 카운트 해준다

구현

---

//컴백홈
public class Main {
	static int R, C, K;
	static char[][] map;
	static boolean[][] visited;
	static int[] dr = {-1, 0, 1, 0};	//상우하좌
	static int[] dc = {0, 1, 0, -1};
	static int res = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		map = new char[R+1][C+1];
		visited = new boolean[R+1][C+1];
		
		for(int i=1; i<=R; i++) {			//맵 입력
			String input = br.readLine();
			for(int j=1; j<=C; j++) {
				char c = input.charAt(j-1);
				map[i][j] = c;
				
				if(c=='T')
					visited[i][j] = true;
			}
		}
		
		visited[R][1] = true;
		dfs(R, 1, 1);
		
		bw.write(res + "");
		bw.flush();
		bw.close();
		br.close();
	}
	
	static void dfs(int r, int c, int depth) {
		if(r==1 && c==C) {
			if(depth==K) res++;
			return;
		}
		
		for(int i=0; i<4; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];
			
			if(1<=nr && nr<=R && 1<=nc && nc <=C) {
				if(visited[nr][nc]) continue;
				visited[nr][nc] = true;
				map[nr][nc] = '-';
				dfs(nr, nc, depth+1);
				visited[nr][nc] = false;
				map[nr][nc] = '.';
			}
		}
	}
}

결과

---