[Java] 백준 1189번 : 컴백홈

1. 문제

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

1189번: 컴백홈

 

 

2. 풀이 과정

1. dfs로 모든 경로 탐색을 한다.

2. 도착점에서 해당 경로가 K면 result+=1 아니면, 해당 경로는 그만 탐색하도록 한다. 또한, 아직 도착점이 오지 않았지만 경로가 이미 K이상이면 더 이상 탐색할 필요가 없으므로 탐색을 종료한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int R, C, K, result;
    static int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    static char map[][];

    public static void dfs(int x, int y, boolean visited[][], int len){
        if(x==0 && y==C-1){
            if(len==K){result++;}
            return;
        }
        if(len >= K){
            return;
        }

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

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputs[] = br.readLine().split(" ");
        R = Integer.parseInt(inputs[0]);
        C = Integer.parseInt(inputs[1]);
        K = Integer.parseInt(inputs[2]);
        map = new char[R][];
        for(int i=0; i<R; i++){
            map[i] = br.readLine().toCharArray();
        }

        boolean visited[][] = new boolean[R][C];
        visited[R-1][0] = true;
        dfs(R-1, 0, visited, 1);
        System.out.println(result);

    }
}

 

결과