[백준] JAVA - 3109.빵집

가스관을 연결할때 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할수있고, 각 칸의 중심끼리 연결합니다. 문제에서 요구하는것이 가장 가스관의 최소 최대 거리가 아니기 때문에 가스관이 갈수있는 경우를 되돌아가서 다시 탐색하지 않는것이 핵심입니다. 

 

그렇기 때문에 백트래킹 방법으로 풀어야합니다. 또한 가스관의 최대 개수를 구해야하므로 가스관이 오른쪽 위 대각선 -> 오른쪽 -> 오른쪽 아래 대각선 순서대로 탐색을 해야 파이프라인의 최대개수를 구할수있습니다.

 

• 3방 탐색을 통해 다음 단계를 탐색하러 들어갑니다. 이때 방문 표시에 대한 흔적을 남겨야 탐색 여부를 판단할수있기 때문에 반드시 해줘야합니다.
• 탐색을 할 수 없는 위치라면 0을 리턴하고 더 이상 이동 할 수없다는 흔적을 남겨줍니다.
• 마지막까지 탐색하여 최종위치에 도달했다면 1을 리턴하여 경우의 수를 누적시켜줍니다.
• 모든 행에 대해 위의 작업을 반복시켜주고 누적된 답을 출력합니다.

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

public class Baekjoon_3109_빵집 {

	static int N,M;
	static char[][] map;
	static boolean[][] visited;
	static int ans;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] init = br.readLine().split(" ");
		N = Integer.parseInt(init[0]);
		M = Integer.parseInt(init[1]);
		map = new char[N][M];
		visited = new boolean[N][M];
		ans = 0;
		
		for (int i = 0; i < N; i++) {
			char[] c = br.readLine().toCharArray();
			for (int j = 0; j < M; j++) {
				map[i][j] = c[j];
			}
		}
		for (int i = 0; i < N; i++) {
			ans += backTracking(i, 0);
		}

		System.out.println(ans);
		
	}
	
	private static int backTracking(int y, int x) {
		if(y < 0 || y >= N || x < 0 || x >= M || map[y][x] != '.') return 0;
		
		if(x == M-1) {
			return 1;
		}
		//가지칠수있는경우
		if(!visited[y][x] && map[y][x] == '.') {
			visited[y][x] = true;
			//위
			if(backTracking(y-1, x+1) == 1) {
				return 1;
			}
			//수평
			if(backTracking(y, x+1) == 1) {
				return 1;
			}
			//아래
			if(backTracking(y+1, x+1) == 1) {
				return 1;
			}
			
		}
		return 0;
		
	}

}