[백준] 3109. 빵집

https://www.acmicpc.net/problem/3109

3109번: 빵집

---

원웅이가 설치할 수 있는 가스관과 빵집을 연결하는 파이프라인의 최대 개수를 구하는 문제입니다. 

첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집입니다. 원웅이의 빵집에서 근처 빵집의 가스관에 몰래 파이프를 설치해야 하는데, 저는 첫째 열의 모든 행에서 차례대로 원웅이의 빵집까지 파이프를 연결할 수 있는지 세는 방식으로 풀었습니다.

파이프는 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 설치할 수 있습니다. 생각해보면 첫째 열에서 위에서부터 차례대로 내려오면서 파이프가 원웅이의 빵집까지 닿을 수 있는 지를 보면 되는데,

무조건 우선적으로 오른쪽 위 대각선 -> 오른쪽 -> 오른쪽 아래 대각선 순으로 연결해야 가스관과 빵집을 연결하는 파이프라인의 최대 개수를 구할 수 있습니다.

그러면 DFS 하는 순서를 오른쪽 위 대각선 -> 오른쪽 -> 오른쪽 아래 대각선 순으로 하면 된다는 것을 알았고, 그 다음에 생각해야 할 것이 우선순위대로 빵집까지 도달했으면 어떻게 재귀적으로 들어온 DFS를 더이상 백트래킹하지 않고 끝내냐? 하는 것입니다.

이 문제는 DFS를 하면서 빵집에 도달했으면 1을 반환하게 하는 void 형이 아닌 int 로 선언하고, 빵집이 있는 마지막 열인 C-1 에 도달했으면 1을 반환하여 그 값이 0이 아니면 계속 return 1을 하게 하여서 빵집에 도달하는 순간 재귀적으로 들어온 모든 DFS를 끝내는 것입니다.

그러면 첫번 째 열의 각 행마다 C-1까지 도달할 수 있는 길을 count 해 줄 수 있고, 마지막에 출력하면 정답입니다.

---

import java.util.Scanner;

public class Main {
		
	static int R, C, result;
	static char[][] map;
	static int[][] dir = {{-1,1},{0,1},{1, 1}};
	static boolean[][] visited;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		R = sc.nextInt();
		C = sc.nextInt();
		map = new char[R][C];
		visited = new boolean[R][C];
		
		for(int i=0; i<R; i++) {
			String str = sc.next();
			map[i] = str.toCharArray();
		}
		
		for(int i=0; i<R; i++) {
			result += recur(i, 0);
		}
		
		System.out.println(result);
	}
	
	public static int recur(int x, int y) {
		visited[x][y] = true;
		
		if(y == C-1) return 1;
		
		for(int i=0; i<3; i++) {
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];
			
			if(isInside(nx, ny) && !visited[nx][ny] && map[nx][ny] == '.') {
				int v = recur(nx, ny);
				if(v != 0) return v;
			}
		}
		return 0;
	}
	
	public static boolean isInside(int x, int y) {
		return x>=0 && x<R && y>=0 && y<C;
	}
}