백준 1189번 컴백홈 JAVA

링크텍스트

설명

시작점: arr[r-1][0],끝점: arr[0][c-1]이다. 백트래킹을 사용해 모든 경우의 수를 구하였다.
시간복잡도: O(4ⁿ), 공간복잡도: O(N²)

코드

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

class Main{
        static int r,c,k;
        static char [][] arr;
		static boolean [][] check;
		static int [] dx = {0,0,-1,1};
		static int [] dy = {1,-1,0,0};
		static int total = 0;
        
	public static void main (String[] args) throws IOException{
	    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());
	    
	    arr = new char[r][c];
		check = new boolean[r][c];

		for(int i=0;i<r;i++){
			String s = br.readLine();
			for(int j=0;j<c;j++){
				arr[i][j]=s.charAt(j);
			}
		}

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

		System.out.println(total);
	}

	public static void dfs(int x,int y,int depth){
		if(x==0 && y==c-1){
			if(depth==k) total++;
			return;
		}

		for(int i=0;i<4;i++){
			int xx = x+dx[i];
			int yy = y+dy[i];

			if(xx>=0 && xx<r && yy>=0 && yy<c && arr[xx][yy]!='T' && !check[xx][yy]){
				check[xx][yy]=true;
				dfs(xx,yy,depth+1);
				check[xx][yy]=false;
			}
		}
	}
}