백준 컴백홈

문제

내가 생각했을때 문제에서 원하는부분

첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다.
두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다.

첫 줄에 거리가 K인 가짓수를 출력한다.

내가 이 문제를 보고 생각해본 부분

T: 못가는길
DFS 사용해서 Visited 배열로 방문 여부 확인
출발 : (R - 1, 0) 이동횟수 == k인 경로의 수
도착 : (0, C - 1)
DFS를 사용해서 출발지에서 도착지까지 이동하는 경로를 찾고 경로들 중 거리가 K인 경로의 수만 구하면 되는 문제이다.
BufferedReader를 사용하여 입력한다.
첫 번째 줄에서 R, C, K 값을 읽고, 맵 정보를 다음 줄부터 읽어 map 배열에 저장한다.
시작점 (R-1, 0)을 방문 처리하고, dfs 메서드를 호출하여 경로 탐색을 시작한다.
마지막으로 answer를 출력한다.
r과 c는 현재 위치, moved는 이동한 거리이다.
현재 위치가 집 (0, C-1)에 도착했을 때, 이동 거리가 K와 같으면 answer를 증가시킨다.
상하좌우로 이동 가능한지 체크하고, 방문하지 않은 곳이면서 장애물('T')이 아닌 경우에만 탐색을 진행한다.
다음 위치로 DFS를 재귀적으로 호출하며, 탐색이 끝난 후에는 방문 기록을 되돌려준다(백트래킹).

코드로 구현

package baekjoon.baekjoon_24;

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

// 백준 1189번 문제
public class Main855 {
    static int R, C, K; // 맵의 행수, 맵의 열 수, 한수가 집까지 가는거리
    static char[][] map; // 맵을 저장하는 2차원 배열(각 칸은 '.' 또는 'T'로 표시)
    static int[][] visited; // 각 칸의 방문 여부를 기록하는 2차원 배열
    static int answer; // 거리 K인 경로의 개수를 저장하는 변수

    // 상하좌우로 이동하기 위한 방향 배열
    static int[] moveR = {1, -1, 0, 0}; // 세로 방향(행) 이동
    static int[] moveC = {0, 0, 1, -1}; // 가로 방향(열) 이동

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] firstLine = br.readLine().split(" ");
        R = Integer.parseInt(firstLine[0]);
        C = Integer.parseInt(firstLine[1]);
        K = Integer.parseInt(firstLine[2]);

        map = new char[R][C];
        visited = new int[R][C];

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

        visited[R - 1][0] = 1; // 시작점 방문 처리
        dfs(R - 1, 0, 1); // DFS 시작
        System.out.println(answer);
        br.close();
    }

    static void dfs(int r, int c, int moved) {
        // 도착
        if(r == 0 && c == C - 1) {
            if(moved == K) {
                answer++;
            }
            return;
        }

        for(int i = 0; i < 4; i++) {
            int nextR = r + moveR[i];
            int nextC = c + moveC[i];
            if(nextR < 0 || nextR >= R || nextC < 0 || nextC >= C)
                continue;
            if(visited[nextR][nextC] == 1 || map[nextR][nextC] == 'T')
                continue;
            visited[nextR][nextC] = 1; // 방문 처리
            dfs(nextR, nextC, moved + 1); // 재귀 호출
            visited[nextR][nextC] = 0; // 백트래킹
        }
    }
}

마무리

코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.