문제

한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.

위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.

입력

첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다.

출력

첫 줄에 거리가 K인 가짓수를 출력한다.

Java

• 한 번만 탐색할 게 아니기 때문에 방문 후, 백트래킹시 visited[nx][ny] = false로 돌린다.

import java.util.*;
import java.io.*;
public class Main {
    static char[][] arr;
    static int R, C, K, cnt=0;
    static boolean[][] visited;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1 };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        C = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        arr = new char[C][R];
        for (int i = 0; i < C; i++) {
            char[] c = br.readLine().toCharArray();
            for (int j = 0; j < R; j++) {
                arr[i][j] = c[j];
            }
        }
        visited = new boolean[C][R];
        visited[C-1][0] = true;
        DFS(C-1, 0, 1);
        System.out.println(cnt);
    }
    public static void DFS(int x, int y, int depth) {
        if (x == 0 && y == R-1) {
            if (depth == K)
                cnt++;
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= C || ny >= R)
                continue;
            if (visited[nx][ny]) {
                continue;
            }
            visited[nx][ny] = true;
            if (arr[nx][ny] == 'T') {
                continue;
            }
            DFS(nx, ny, depth + 1);
            visited[nx][ny] = false;
        }
    }
}