[백준][JAVA] - 컴백홈(1189)
문제 소개
🥈 문제 레벨 : 실버1
🔔 문제 유형 : 백트래킹, 깊이 우선 탐색
💬 풀이 언어 : JAVA
⏱️ 풀이 시간 : 10분
🖇️ 문제 링크 : 백준 문제 링크
📝 문제
한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.
cdef ...f ..ef ..gh cdeh cdej ...f
bT.. .T.e .Td. .Tfe bTfg bTfi .Tde
a... abcd abc. abcd a... a.gh abc.
거리 : 6 6 6 8 8 10 6
위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.
🤔 문제 분석
기존 DFS에 백트래킹이 얹어진 문제라고 생각한다.
R, C, K가 주어지고, (R - 1, 0)에서 시작해 (0, C - 1)까지 K번의 움직임으로 갈 수 있는 방법이 총 몇 가지가 있는지 구하면 된다.
문제에서 주어진 예시에서 3번째 케이스와 4번째 케이스를 보면, abc까지는 같지만, d의 위치가 다른 것을 볼 수 있다.
즉, 현재 좌표에서 모든 방향으로 가는 가능성을 모두 따져야하는 것이다.
😎 최종 코드
메모리 : 12328 KB
시간 : 92 ms
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int H, W, K, result;
static char[][] map;
static boolean[][] visited;
static int[] dx = {1, 0, -1, 0}, dy = {0, -1, 0, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// R(H), C(W), K
StringTokenizer st = new StringTokenizer(br.readLine());
H = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
// 지도 배열 초기화
map = new char[H][W];
for (int i = 0; i < H; i++) {
char[] charArray = br.readLine().toCharArray();
for (int j = 0; j < W; j++) {
map[i][j] = charArray[j];
}
}
// 방문 배열 초기화 및 시작 위치 방문 처리
visited = new boolean[H][W];
visited[H - 1][0] = true;
// 한수 현재 위치부터 탐색 시작
dfs(H - 1, 0, 1);
System.out.println(result);
}
private static void dfs(int y, int x, int cnt) {
// 이동 횟수가 K와 같을 경우
if (cnt == K) {
// 현재 좌표가 목적지와 같을 경우 결과값 증가
if(y == 0 && x == W - 1) result++;
// 아닐 경우 돌아가기
return;
}
// 현재 위치에서 네 방향 탐색
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < W && ny >= 0 && ny < H) {
if (!visited[ny][nx] && map[ny][nx] == '.') {
// 다음 좌표 미리 방문 처리
visited[ny][nx] = true;
// 다음 좌표로 탐색
dfs(ny, nx, cnt + 1);
// 탐색을 마쳤다면 다음 좌표 방문처리 해제
visited[ny][nx] = false;
}
}
}
}
}
댓글남기기