[백준/Java] 1189번 컴백홈

🔗 문제 링크: https://www.acmicpc.net/problem/1189

🔍 해결 과정

왼쪽 아래에서 오른쪽 위까지의 다양한 경로 중 k번 이동한 경로와 일치한 경우의 수를 구하는 문제이고, R과 C의 최댓값이 5이므로 dfs(Depth-First Search) 방식을 활용하여 오른쪽 위에 도달했을 때 k번 이동했는지의 경우를 확인하고 일치하면 경우를 세어주는 과정으로 코드를 구현하였습니다. dfs를 활용했을 때 O(R x C) 의 시간복잡도를 가지므로 제한 시간 안에 프로그램을 실행할 수가 있습니다.

 

---

✏️ 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    private static final char BLOCK = 'T';
    private static final int[] DX = {-1, 0, 1, 0};
    private static final int[] DY = {0, 1, 0, -1};

    private static int r, c, k;
    private static char[][] board;
    private static boolean[][] visited;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken()); // 이동하는 가짓수
        board = new char[r][c];
        visited = new boolean[r][c];

        for (int i = 0; i < r; ++i) {
            board[i] = br.readLine().toCharArray();
        }

        int startR = r - 1;
        int startC = 0;
        int endR = 0;
        int endC = c - 1;

        bw.write(Integer.toString(getResult(startR, startC, endR, endC, 1)));
        bw.flush();
        bw.close();
    }

    private static int getResult(int curR, int curC,
                                 final int endR, final int endC, int step) {
        if (curR == endR && curC == endC) {
            if (step == k) {
                return 1;
            }
            return 0;
        }

        int count = 0;
        visited[curR][curC] = true;
        for (int dir = 0; dir < 4; ++dir) {
            int nx = curR + DX[dir];
            int ny = curC + DY[dir];

            if (!isValid(nx, ny)) {
                continue;
            }

            count += getResult(nx, ny, endR, endC, step + 1);
        }
        visited[curR][curC] = false;
        return count;
    }

    private static boolean isValid(int x, int y) {
        return !(x < 0 || y < 0 || x >= r || y >= c) && !visited[x][y] && board[x][y] != BLOCK;
    }
}