문제
R x C 격자에서 왼쪽 아래에서 오른쪽 위까지 정확히 K칸을 거쳐 이동하는 경로의 수를 구하라. T는 장애물이다.
입력
첫째 줄에 R, C, K, 이후 R줄에 격자가 주어진다.
출력
거리가 정확히 K인 경로의 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 4 6 .... .T.. .... | 4 |
풀이
DFS 백트래킹으로 시작점에서 목표점까지 정확히 K칸 이동하는 모든 경로를 탐색한다.
- (R-1, 0)에서 출발하여 (0, C-1)을 목표로 DFS를 수행한다
- 방문 체크 배열로 같은 칸 재방문을 방지한다
- 목표 도달 시 이동 거리가 정확히 K이면 카운트한다
- 백트래킹으로 방문을 해제하며 모든 경로를 탐색한다
핵심 아이디어: R, C가 최대 5이므로 격자가 매우 작아 백트래킹 전수 탐색이 가능하다.
코드
package day799;
import java.io.*;
import java.util.*;
public class Day755BOJ1189컴백홈 {
static int R, C, K, ans;
static char[][] map;
static int[][] visited;
static int[] dr = { 1, -1, 0, 0 }, dc = { 0, 0, 1, -1 };
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());
map = new char[R][C];
visited = new int[R][C];
for (int i = 0; i < R; i++) {
String s = br.readLine();
for (int j = 0; j < C; j++) {
map[i][j] = s.charAt(j);
}
}
visited[R - 1][0] = 1;
dfs(R - 1, 0, 1);
System.out.println(ans);
}
static void dfs(int r, int c, int moved) {
if (r == 0 && c == C - 1) {
if (moved == K) {
ans++;
}
return;
}
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) {
continue;
}
if (visited[nr][nc] == 1 || map[nr][nc] == 'T') {
continue;
}
visited[nr][nc] = 1;
dfs(nr, nc, moved + 1);
visited[nr][nc] = 0;
}
}
}복잡도
- 시간: O(4^K) - 최악 경우 모든 경로 탐색
- 공간: O(R*C)