[백준]3109번 빵집(Java)

문제

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

3109번: 빵집

---

풀이

알고리즘: 백트래킹, DFS

0행에서는 아무곳에서나 출발 할 수 있으므로 R길이만큼 돌며 깊이우선탐색 알고리즘을 실행한다.

탐색의 기저조건은 현재 Column이 마지막 Column일때.

그 외에는 삼방탐색을 하여 갈 곳을 정한다.

이 때, 지나온 곳은 'O'로 표시하여 다시 지나갈 수 없게 한다.

하나의 파이프라인이 만들어졌을 때(기저조건) 해당 칸에서 다시 탐색이 이루어지지 않도록 Flag를 사용한다. (백트래킹)

 

사실 아직 ,, 백트래킹 개념을 확실히 잘 모르겠다 ,, 또 일반 조합 알고리즘이랑 DFS차이도 모르겠다 ,, 

갈길이 너무 멀다,, இ௰இ

 

코드

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

public class Main{
	static int R, C, cnt;
	static char[][] map;		//맵 정보 저장
	static int[] di = {-1,0,1};		//우상, 우, 우하
	static int[] dj = {1,1,1};
	static boolean flag = false;	//백트래킹 flag

	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];
		cnt = 0;
		for(int i =0 ; i < R ; i++) {
			String str = br.readLine();
			for(int j =0 ; j < C ; j++) {
				map[i][j] = str.charAt(j);
			}
		}
		for(int i = 0 ; i< R ; i++) {		//0행에서 R-1행까지 탐색
			flag = false;		
			setPipe(i, 0);		//깊이 우선 탐색
		}
		System.out.println(cnt);
	}
	
	private static void setPipe(int rowNo, int colNo) {
		if(colNo == C-1) {		//기저조건
			map[rowNo][colNo] = 'O';	
			flag = true;	//해당 경로에서의 경우의 수 탐색이 종료되었음을 알림
			cnt++;	
			return;
		}
		for(int i =0 ; i < 3 ; i++) {		//삼방탐색
			int ni = rowNo + di[i];
			int nj = colNo + dj[i];
			if(0<=ni&&ni<R && 0<=nj&&nj<C && map[ni][nj] == '.') {
				map[rowNo][colNo] = 'O';	
				setPipe(ni, nj);	//깊이 우선 탐색
				if(flag) return;		//해당 경로에서 더이상 탐색하지 않도록
			}
		}
	}
}