Baekjoon 1189 컴백홈 JAVA

1189번: 컴백홈

문제

한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.

      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인 가짓수를 구하는 것이다.

입력

첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다.

출력

첫 줄에 거리가 K인 가짓수를 출력한다.

풀이

K 거리를 가지면서 가장 오른쪽 위에 도달하는 경로를 찾는다.

여기서 본인은 DFS방식을 이용하였다.

이동거리가 K보다 커진다면 그 이상으로 이동하는 거리는 답이 될 수 없기에, 탐색을 종료한다.

 

DFS로 이동하면서 거리가 K임을 판단하고, 거리가 K이면서 현재 위치가 가장 오른쪽 위일때 조건을 만족하기에

답을 1증가시키면서 전체로 갈 수 있는 경우의 수를 찾는다.

코드

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

public class Main {
	static int ans,r,c,k;
	static int [] dx= {1,-1,0,0}, dy= {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());
		boolean [][] map = new boolean [r][c];
		for(int i=0;i<r;i++) {
			String str = br.readLine();
			for(int j=0;j<c;j++)
				if(str.charAt(j)=='T')	// T로 막힌 부분은 탐색시 이미 방문했다고 처리하면 그 위치는 탐색하지 않음
					map[i][j]=true;
		}
		map[r-1][0]=true;	// 시작점 방문 처리
		DFS(map, r-1,0,1);
		System.out.println(ans);
	}
	public static void DFS(boolean[][]map, int x,int y, int d) {
		if(d>=k) {	// 방문한 수가 이미 D보다 크면 추가 탐색하지 않음
			if(x==0 && y==c-1 && d==k)	// 도착 위치이면서 방문횟수가 K랑 같을때만 경로수 추가
				ans++;
			return;	// 추가 탐색 X
		}
		for(int i=0;i<4;i++) {	// DFS 방식으로 탐색
			if(x+dx[i]>=0 && x+dx[i]<r && y+dy[i]>=0 && y+dy[i]<c) {
				if(!map[x+dx[i]][y+dy[i]]) {
					map[x+dx[i]][y+dy[i]]=true;
					DFS(map, x+dx[i], y+dy[i], d+1);
					map[x+dx[i]][y+dy[i]]=false;
				}
			}
		}
	}
}