[백트래킹 | DFS] 빵집(백준 3109번, 자바)☆☆☆

Main_3109_빵집.pdf

0.22MB

 

 

 

 

 

 

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

public class Main_3109 {
	
	static int[] dx= {-1,0,1};
	static int[] dy= {1,1,1};
	static char[][] c;
	static boolean[][] visit;
	static int R,C;
	static int answer=0;
	static boolean check=false;
	
	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());
		String s;
		
		c=new char[R][C];
		visit=new boolean[R][C];
		
		for(int i=0;i<R;i++){
			s=br.readLine();
			c[i]=s.toCharArray();
		}
		for(int i=0;i<R;i++) {
			if(c[i][0]!='x') {
				check=false; 
				dfs(i,0);
			}
		}
		System.out.println(answer);
		
	}	
	
	static void dfs( int x, int y) {
		
		if(y==C-1) {
			check=true;
			answer++;
			return;
		}
		
		for(int i=0;i<3;i++) {
			int nx=x+dx[i];
			int ny=y+dy[i];
			if(nx<0 || ny<0 || nx>=R || ny>=C || visit[nx][ny] || c[nx][ny]=='x') continue;
			visit[nx][ny]=true;
			dfs(nx,ny);
			if(check) return;
			
		}
	}
	


}