[백준 3109 - JAVA] 빵집

3109번: 빵집

 

스터디 과제로 나왔지만, 예전에 풀었던 문제라서 코드를 보면서 복기만 해봤다.

dfs를 이용했고, 모든 시작점에서 출발하여 파이프를 연결할 수 있을 경우 계속 진행하는 백트래킹 방식으로 풀었다. 

 

풀이 방법

1. 행의 수 만큼 dfs를 시작한다.

2. 오른쪽위, 오른쪽, 오른쪽 아래로 이동하며 범위안이며 건물이 아닐 경우에만 dfs를 진행한다.

3. 열의 끝에 도달한 경우 ans를 증가시킨다.

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


public class Main {

	public static int R, C, ans;
	public static int[] dx = {-1, 0, 1};
	public static char[][] map;
	
	
	public static boolean dfs(int x, int y) {
		if (y == C-1) {
			ans++;
			return true;
		}
		
		int nx, ny;
		for (int i = 0; i < 3; i++) {
			nx = x+dx[i];
			ny = y+1;
			
			if (isBoundary(nx, ny) && map[nx][ny] == '.') {
				map[nx][ny] = 'x';
				if (dfs(nx, ny))
					return true;
			}
		}
		
		return false;
	}
	
	public static boolean isBoundary(int nx, int ny) {
		if (nx < 0 || nx >= R || ny < 0 || ny >= C)
			return false;
		return true;
	}
	
	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());
		
		map = new char[R][C];		
		String str;
		for (int i = 0; i < R; i++) {
			str = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = str.charAt(j);
			}
		}
		
		for (int i = 0; i < R; i++) {
			dfs(i, 0);
		}
		System.out.println(ans);
		
	}
}