[백준] | JAVA, 자바 | 1189번 - 컴백홈

https://www.acmicpc.net/problem/1189

---

문제 요약 :

1. 첫 줄에 정수 R (1 <= R <= 5), C ( 1 <= C <= 5 ), K ( 1 <= K <= RxC )가 공백으로 구분되어 주어진다.

2. 두 번째부터 R + 1번째 줄까지는 RxC 맵의 정보가 주어진다.

3. 시작점 : 왼쪽 아래 점 -> 목표 지점 : 오른쪽 위 집

4. 한번 지나간 곳은 다시 방문하지 않는다.

5. T로 표시된 부분은 가지 못하는 부분이다.

6. 한수가 집까지 도착하는 경우 중 거리가 K인 가짓수를 구하라.

---

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

public class Main {
    private static int R, C, K, result;
    private static char[][] map;
    private static final int[][] delta = {{-1,0},{1,0},{0,-1},{0,1}}; // 상, 하, 좌, 우
    private static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 1. 첫 줄에 정수 R, C, K 입력 받기
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        visited = new boolean[R][C];
        result = 0;

        // 2. R x C 맵 정보 입력받기
        for (int i = 0; i < R; i++) {
            String line = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = line.charAt(j);
            }
        }

        // 시작 지점 : 왼쪽 아래점 : R - 1, 0 / 목표 지점 : 오른쪽 위 : 0, C - 1
        // 3. 시작 지점부터 탐색 시작
        visited[R-1][0] = true;
        move(R - 1, 0, 1);

        // 4. 결과 출력
        System.out.println(result);
    }
    
    private static void move(int x, int y, int cnt) {
        if (x == 0 && y == C - 1) {
            // 3-3. K번 만큼 이동했을 때, 목표지점이라면 result++;
            if (cnt == K) result++;
            return;
        }

        // 3-1. 사방탐색을 진행
        for (int i = 0; i < 4; i++) {
            int nr = x + delta[i][0];
            int nc = y + delta[i][1];

            // 3-2. 범위를 벗어나지 않고, 방문을 하지 않았고, T가 아니라면 방문처리 후 계속 이동
            if (isRange(nr, nc) && !visited[nr][nc] && map[nr][nc] != 'T') {
                visited[nr][nc] = true;
                move(nr, nc, cnt + 1);
                visited[nr][nc] = false;
            }
        }
    }

    private static boolean isRange(int nr, int nc) {
        return nr >= 0 && nr < R && nc >= 0 && nc < C;
    }
}