백준 1189번 <컴백홈>

백준 알고리즘 1189번

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

1189번: 컴백홈

---

1189번

한수는 현재 왼쪽 아래 점에 있고 집은 오른쪽 위에 있다. 한수가 집으로 돌아가는 방법은 다양하지만 한 번 지나친 곳을 다시 시 방문하지 않는다. R x C 맵에 못가는 부분이 주어지고 거리 K가 주어졌을 때, 한수가 집까지 도착하는 경우 중 거리가 K인 가짓수를 구하여라.

 

입력으로 첫 줄이 R, C, K가 공백으로 구분되어 주어진다. 그 다음 R개의 줄에 걸쳐 R x C 맵의 정보가 주어진다. (T는 갈 수 없는 곳)

 

출력으로 한수가 집까지 가는 경우 중 거리가 K인 가짓수를 출력하면 된다.

---

문제 해결

DFS를 사용하여 문제를 해결하였다.

먼저 K 거리인 경우만 구하는 것이기 때문에 K보다 멀리 가는 경우는 가지치기를 해주었다.

그리고 인접한 4 방향(상, 하, 좌, 우)으로 갈 수 있다면 DFS 함수를 재귀 호출하였다.

재귀 호출 전에 오른쪽 위에 도착하는 경우를 판별하여 가짓수를 update 해주었다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
	static int R, C, K, ans;
	static char[][] map;
	static int[] di = { -1, 1, 0, 0 };
	static int[] dj = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] inArr = br.readLine().split(" ");
		R = Integer.parseInt(inArr[0]);
		C = Integer.parseInt(inArr[1]);
		K = Integer.parseInt(inArr[2]);
		map = new char[R][];
		for (int i = 0; i < R; i++) {
			map[i] = br.readLine().toCharArray();
		} // end input
		ans = 0;
		DFS(R - 1, 0, 1, new boolean[R][C]);
		System.out.println(ans);
	}

	public static void DFS(int i, int j, int dist, boolean[][] visit) {
		if (dist > K) {
			return;
		}
		visit[i][j] = true;

		for (int k = 0; k < 4; k++) {
			int ni = i + di[k];
			int nj = j + dj[k];

			if (ni < 0 || nj < 0 || ni >= R || nj >= C || visit[ni][nj]) {
				continue;
			}
			if (map[ni][nj] == 'T') {
				continue;
			}
			if (ni == 0 && nj == C - 1) {
				if (dist + 1 == K) {
					ans++;
				}
				continue;
			}
			DFS(ni, nj, dist + 1, copy(visit));
		}
	}

	public static boolean[][] copy(boolean[][] visit) {
		boolean[][] arr = new boolean[R][C];
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				arr[i][j] = visit[i][j];
			}
		}
		return arr;
	}

}

---

결과

---