1189번: 컴백홈

문제

한수는 캠프를 마치고 집에 돌아가려 합니다. 한수는 현재 왼쪽 아래 점에 있고 집은 오른쪽 위 점에 있습니다. 지도는 R x C 크기이며, 빈칸은 '.'이고 가지 못하는 칸은 'T'로 표시되어 있습니다. 한수가 거리가 딱 K인 경로로 집에 돌아가는 모든 경우의 수를 구하는 문제입니다.

• 입력: 첫째 줄에 R, C, K가 주어집니다. (1 ≤ R, C ≤ 5, 1 ≤ K ≤ R×C) 다음 R개의 줄에 맵의 정보가 주어집니다.
• 출력: 거리가 K인 경로의 수를 출력합니다.

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

풀이: 백트래킹을 활용한 모든 경로 탐색

거리가 정확히 K인 모든 경로의 수를 구해야 하므로, 전형적인 DFS와 백트래킹을 결합한 완전탐색 문제입니다.

1. 시작점 및 방문 처리: 한수의 시작 위치는 맵의 왼쪽 아래인 (R - 1, 0)입니다. 시작점도 거리에 포함되므로 visited 처리를 하고 초기 거리를 1로 두어 DFS 탐색을 시작합니다.
2. 기저 조건 (종료 조건): 이동한 거리 d가 목표 거리 k와 같아지면 탐색을 멈춰야 합니다. 이때 현재 위치가 집의 위치인 맵의 오른쪽 위 (0, C - 1)이라면 정답(ans)을 1 증가시킵니다. 목표 거리에 도달했다면 위치에 상관없이 무조건 return하여 탐색을 종료합니다.
3. 백트래킹 (원상 복구): 4방향으로 탐색을 진행하며, 맵을 벗어나거나 방해물('T')이 있거나 이미 방문한 곳이라면 건너뜁니다. 조건을 만족하면 visited[ny][nx] = true로 방문 처리를 한 후 dfs(ny, nx, d + 1)을 호출하여 다음 칸으로 넘어갑니다. 탐색을 마치고 돌아왔을 때는 다른 방향으로의 새로운 경로를 찾기 위해 반드시 visited[ny][nx] = false로 되돌려놓아야 합니다.

코드

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

public class Main {
    static int r, c, k, ans;
    static char[][] a;
    static boolean[][] visited;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    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());
       a = new char[r][c];

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

       visited = new boolean[r][c];
       // 시작 위치 (왼쪽 아래) 방문 처리 및 탐색 시작
       visited[r - 1][0] = true;
       dfs(r - 1, 0, 1);

       bw.write(ans + "");
       bw.flush();
    }

    static void dfs(int y, int x, int d) {
       // 이동 거리가 k에 도달했을 때
       if (d == k) {
          // 현재 위치가 도착지 (오른쪽 위)라면 정답 증가
          if (y == 0 && x == c - 1) {
             ans++;
          }
          return;
       }

       for (int i = 0; i < 4; i++) {
          int ny = y + dy[i];
          int nx = x + dx[i];
          
          // 맵을 벗어나면 무시
          if (ny < 0 || nx < 0 || ny >= r || nx >= c)
             continue;
          // 장애물('T')이거나 이미 방문한 곳이면 무시
          if (a[ny][nx] == 'T' || visited[ny][nx])
             continue;
             
          // 방문 처리 후 다음 탐색
          visited[ny][nx] = true;
          dfs(ny, nx, d + 1);
          // 다른 경로를 찾기 위한 백트래킹
          visited[ny][nx] = false;
       }
    }
}

알고리즘 분류

그래프 탐색, 깊이 우선 탐색 (DFS), 백트래킹 (Backtracking)