백준 1189번 컴백홈(java)

[Silver I] 컴백홈 - 1189

문제 링크

성능 요약

메모리: 14888 KB, 시간: 124 ms

분류

백트래킹, 브루트포스 알고리즘, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 7월 29일 22:27:25

문제 설명

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

      cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f 
      bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde 
      a...  abcd  abc.  abcd  a...  a.gh  abc. 
거리 :  6     6     6     8     8    10    6

위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. 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인 가짓수를 출력한다.

풀이

최단 거리를 찾는 경우라면 오른쪽과 위로만 움직이면 된다. 하지만 최단 거리가 아닌 사용자가 입력한 값과 똑같은 거리로 가는 방법을 찾는 문제이므로 상,하,좌,우 모두 움직여보며 오른쪽위에 도달하는 경우를 전부 찾아야한다.

 

왔던 길을 되돌아가는 경우는 없다고 하니 visited [][] 배열을 활용하여 왔던 길로 되돌아가지 않게 하였고,

 

거리가 K 이상인데 목표 지점에 도달하지 못한 경우는 더 탐색을 해도 의미가 없기에 바로 return 시켜줬다

 

상,하,좌,우로 모두 재귀함수 호출을 하여 모든 가짓수를 체크했다.

전체 코드

public class Main{
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int R,C,K,cnt=0;
    static char x[][];
    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());

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        x = new char[R][C];
        visited = new boolean[R][C];

        for(int  i = 0 ;i<R;i++){
            char in[] = br.readLine().toCharArray();
            for(int j = 0 ;j<C;j++){
                x[i][j] = in[j];
                visited[i][j] = true;
            }
        }
        visited[R-1][0] = false;
        dfs(1,R-1,0);

        bw.write(String.valueOf(cnt));
        bw.flush();
    }

    public static void dfs(int depth, int Y, int X){

        if(depth == K){
            if(Y == 0 && X == C-1){
                cnt++;
            }
            return;
        }

        if(Y > 0 && x[Y-1][X] != 'T' && visited[Y-1][X]){
            visited[Y-1][X] = false;
            dfs(depth+1, Y-1,X);
            visited[Y-1][X] = true;
        }
        if(X < C-1 && x[Y][X+1] != 'T' && visited[Y][X+1]){
            visited[Y][X+1] = false;
            dfs(depth+1,Y,X+1);
            visited[Y][X+1] = true;
        }
        if(Y < R-1 && x[Y+1][X] != 'T' && visited[Y+1][X]){
            visited[Y+1][X] = false;
            dfs(depth+1,Y+1,X);
            visited[Y+1][X] = true;
        }
        if(X > 0 && x[Y][X-1] != 'T' && visited[Y][X-1]){
            visited[Y][X-1] = false;
            dfs(depth+1,Y,X-1);
            visited[Y][X-1] = true;
        }


    }


}