백준 1189 컴백홈 자바(java)

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

1189번: 컴백홈

 

풀이 방법

DFS + 백트래킹을 사용하여 풀었다.

왼쪽 아래 시작점부터 방문 체크를 해가면서 한 칸씩 이동하여 오른쪽 위 집에 도착했을 때 거리가 K이면 카운트한다. 현재 칸에서 인접한 상하좌우 칸 중 T가 아니고 방문을 하지 않은 칸이면 이동할 수 있으며 이동했을 때 재방문하지 않도록 해당 칸은 방문 체크를 해준다. 이때, 탐색을 완료한 후 다시 돌아왔을 때 이전에 방문 체크했던 것을 다시 False 로 되돌려놓음으로써 다른 방향으로도 탐색이 가능하도록 해야 한다.

 

코드

import java.io.*;

public class Main {

    static int R;
    static int C;
    static int K;
    static String[][] map;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static boolean[][] visited;
    static int answer = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        R = Integer.parseInt(line[0]);
        C = Integer.parseInt(line[1]);
        K = Integer.parseInt(line[2]);

        visited = new boolean[R][C];
        map = new String[R][C];
        for(int i=0; i<R; i++) {
            String row = br.readLine();
            for(int j=0; j<C; j++) {
                map[i][j] = row.substring(j, j+1);
            }
        }

        dfs(R-1, 0, 1);
        System.out.println(answer);
    }

    public static void dfs(int x, int y, int d) {
        // 집에 도착
        if(x == 0 && y == C-1) {
            if(d == K) {
                answer++;
            }
            return;
        }

        if(d == K) {
            return;
        }

        visited[x][y] = true;

        for(int k=0; k<4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(nx < 0 || nx >= R || ny < 0 || ny >= C) {
                continue;
            }
            // 갈 수 있으면
            if(!visited[nx][ny] && !map[nx][ny].equals("T")) {
                dfs(nx, ny, d+1);
            }
        }

        visited[x][y] = false;
    }
}