[백준] 1189번 컴백홈 자바 풀이

문제

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

2 초

128 MB

7011

3924

3058

55.109%

문제

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

      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인 가짓수를 출력한다.

풀이

R,C의 범위가 매우 작으므로 DFS를 활용하여 문제를 풀었다.

왼쪽 아래 (r-1, 0) 부터 오른쪽 위 (0, c-1) 까지 이동하는 경우 중 k번의 이동으로 도달 가능한 갯수를 작성하는 문제이므로 (r-1, 0) 부터 (0, c-1) 까지 depth를 늘려가며 1칸씩 이동하도록 해줬다. 별다른 어려움은 없이 풀었다.

코드

package com.company.baekjoon;

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

public class B1189 {
    static int[] dx = new int[] {-1,1,0,0};
    static int[] dy = new int[] {0,0,-1,1};
    static int r;
    static int c;
    static int k;
    static int[][] arr;
    static boolean[][] visited;

    static int count;

    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());

        arr = new int[r][c];
        visited = new boolean[r][c];

        for (int i = 0; i < r; i++) {
            st = new StringTokenizer(br.readLine());
            String s = st.nextToken();
            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(j) == '.') {
                    arr[i][j] = 0;
                } else {
                    arr[i][j] = 1;
                }
            }
        }
        visited[r-1][0] = true;
        dfs(r-1, 0, 1);
        System.out.println(count);
    }
    public static void dfs(int i, int j, int depth) {
        if (i == 0 && j == c-1) {
            if (depth == k) count++;
            return;
        }
        for (int l = 0; l < dy.length; l++) {
            int ny = i + dy[l];
            int nx = j + dx[l];

            if (ny < 0 || nx < 0 || ny >= r || nx >= c) continue;
            if (visited[ny][nx]) continue;
            if (arr[ny][nx] == 1) continue;
            visited[ny][nx] = true;
            dfs(ny, nx, depth + 1);
            visited[ny][nx] = false;
        }
    }
}