[백준] 1189: 컴백홈 - JAVA

15 Oct 2023 in Algorithm on 그래프 이론

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

풀이

(R-1, 0)에서 (0, C-1)로 이동한다. T는 가지 못하는 부분이고, 한번 지나친 곳은 다시 방문하지 않는다.

이동거리가 K인 경우의 수를 구하는 문제이다.

따라서 방문처리를 하며 dfs탐색을 했다. 각각의 경우에 따른 방문처리가 서로 영향을 주어서는 안되기 때문이다.

이동 거리를 1씩 늘려가면서 다음 칸으로 이동했고, 이동 거리가 K가 됐을 때, 도착점에 도달하였을 때 사이클을 종료시켰다.

---

메모리: 14584KB

시간: 136ms

언어: Java 11

코드

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

public class Main {
    static int[][] vector = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
    static int R, C, K, ans = 0;
    static char[][] board;
    static boolean[][] visit;

    public static void main(String[] args) throws Exception {
        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());

        board = new char[R][C];
        for (int i = 0; i < R; i++) {
            board[i] = br.readLine().toCharArray();
        }

        visit = new boolean[R][C];
        visit[R - 1][0] = true;
        dfs(R - 1, 0, 1);

        System.out.println(ans);
    }

    private static void dfs(int r, int c, int cnt) {
        if (r == 0 && c == C - 1) {
            if (cnt == K) {
                ans++;
            }
            return;
        }

        if (cnt == K) {
            if (r == 0 && c == C - 1) {
                ans++;
            }
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nr = r + vector[i][0];
            int nc = c + vector[i][1];

            if (!isPossible(nr, nc)) {
                continue;
            }

            visit[nr][nc] = true;
            dfs(nr, nc, cnt + 1);
            visit[nr][nc] = false;
        }

    }

    private static boolean isPossible(int nr, int nc) {
        if (nr < 0 || nc < 0 || nr >= R || nc >= C) {
            return false;
        }

        if (board[nr][nc] == 'T' || visit[nr][nc]) {
            return false;
        }

        return true;
    }

}