[BJ] 3109. 빵집

[BJ] 3109. 빵집

www.acmicpc.net/problem/3109

3109번: 빵집

 

이것또한 나를 오래 괴롭혔던 백트래킹 문제다.. 가지치기 1번을 하는 이유를 이해하지 못했는데 하나하나 그림을 그려보다 이해했다. 역시 이해 안될 때는 해보는게 최고다.

 

1. 가지치기1 :  dfs 탐색을 하다가 마지막 열까지 간다면, true를 반환하거나 false를 반환하는 작업을 통하여 더 이상의 탐색을 멈추는 가지치기를 수행하여야 한다.

예를 들어, d = 0에서 dfs 탐색을 하여 파이프 놓기에 성공한 경우. 더 아래 행 방향인 d = 1, 2 으로 탐색할 필요가 없다! 파이프는 위에서부터 놓을 때 가장 많이 놓을 수 있기 때문이다.

2.  가지치기2: 3방 탐색이 모두 불가능한 경우라도 visited[r][c]값을 false로 초기화 해주어서는 안된다. 더 이상의 탐색이 불가능한 위치라면, 밑의 행에서 방문했을 때 똑같이 탐색이 불가능하다.

 

import java.io.*;
import java.util.*;
// 210306

public class Main_BJ_3109_빵집 {
	static int R, C, cnt=0;
	static char[][] map;
	static boolean[][] visited;
	static char pipe = 'p';

	static int stoi(String str) {
		return Integer.parseInt(str);
	}
	
	// 디버깅용
	static void printMap() {
		for(int i=0; i<R; i++) {
			System.out.println(Arrays.toString(map[i]));
		}
		System.out.println("=========================");
	} // 
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_BJ_3109_빵집.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		R = stoi(st.nextToken());
		C = stoi(st.nextToken());
		map = new char[R][C]; // 0번 0행부터 시작 
		// 0열은 가스관, C-1열은 가게이다.
		visited = new boolean[R][C];
		
		for(int i=0; i<R; i++) {
			map[i] = br.readLine().toCharArray();
		}
		makePipe();
		System.out.println(cnt);

		br.close();
	} // main

	static void makePipe() {
		// 0행부터 파이프 놓기 시도
		for(int r=0; r<R; r++) {
			pipe = (char)(r + '0'); // int ->  char
			map[r][0] = pipe; // 디버깅용
			
			visited[r][0] = true; // 0행은 가스관
			dfs(r, 0); // r행의 0열부터 dfs 탐색	
			
			// 디버깅
			// 한 행부터 파이프 놓기를 시도한 결과를 출력한다.
//			System.out.println(r+"행에서 시도, cnt = " + cnt);
//			printMap();
		}
	} // 
	
	static int[] dr = {-1, 0, 1}; // 우상, 우, 우하 순
	static boolean dfs(int r, int c) {
		if(c==(C-1)) {
			++cnt;
			return true; 
			// 파이프 놓기 성공
		}
		
		int nc = c+1; // ->
		for(int d=0; d<3; d++) {
			int nr = r + dr[d];
			if(nr<0 || nr>=R || visited[nr][nc] || map[nr][nc]!='.') 
				continue; // 파이프를 놓을 수 없는 경우 다음 (d+1) 방향 탐색
			// 파이프를 놓을 수 있는 경우 
			map[nr][nc] = pipe; // 디버깅용
			if(dfs(nr, nc)) return true; 
			// 1. 파이프 놓기에 성공할 경우 true를 리턴하여 다음 (d+1) 방향을 탐색하지 않도록 가지치기
		}
		return false; // 2. 세방향 어디로도 가지 못한다면 가지치기. 
					  // (r, c)에서 더이상 파이프를 놓을 수없다면 r+N 행에서도 놓을 수 없다.
	}
}