[Baekjoon] 1189_컴백홈

Silver I

문제(출처: https://www.acmicpc.net/problem/1189)

---

< 컴백홈 >

 

문제 풀이 

 

dfs를 활용하여 거리가 k인 가짓수를 구한다.

 

 

 my solution (Java)

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

public class _1189_ { // 컴백홈
	static int result, k;
	static boolean visited[][];
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };

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

		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());

		visited = new boolean[r][c];
		result = 0;
		for (int i = 0; i < r; i++) {
			String str = bf.readLine();
			for (int j = 0; j < c; j++) {
				if(str.charAt(j)=='T') {
					visited[i][j]=true;
				}
			}
		}

		visited[r - 1][0] = true;
		dfs(r - 1, 0, 1);

		System.out.println(result);
	}

	private static void dfs(int x, int y, int d) {
		if (d + 1 > k)
			return;
		for (int i = 0; i < 4; i++) {
			int mx = x + dx[i];
			int my = y + dy[i];
			if (mx >= 0 && mx < visited.length && my >= 0 && my < visited[0].length && !visited[mx][my]) {
				if (mx == 0 && my == visited[0].length - 1 && d + 1 == k) {
					result += 1;
					return;
				}
				visited[mx][my] = true;
				dfs(mx, my, d + 1);
				visited[mx][my] = false;
			}
		}
	}
}

변수)
r, c , k : 맵 크기, 거리 k
visited : 방문 여부
result : 거리가 K인 가짓수

 

RxC맵의 정보를 입력받아 T로 표시된 부분은 가지 못하는 부분이므로 방문 여부를 true로 저장한다. 왼쪽 아래점부터 시작하므로 왼쪽 아래 위치도 방문 여부를 true로 저장 후 dfs 함수를 호출한다. 

 

거리가 k보다 크다면 정답과 상관없으므로 종료한다. k보다 크지 않다면 상하좌우로 이동했을 때의 좌표를 구한다. 좌표가 맵을 벗어나지 않으며 아직 방문하지 않은 곳이라면 그 위치로 이동한다. 만약 그 위치가 오른쪽 위 도착 지점이며 거리가 k라면 정답이므로 result+1해 주며 종료한다. 도착 지점이 아니라 이동 가능한 곳이라면 방문 표시를 해준 후 dfs 함수를 호출한다.

 

최종 정답인 result를 출력한다.

---

---