백준 3109번 빵집

풀이방법

먼저 맵을 입력받고 dfs를 호출했다.
왼쪽 열에서 맨 오른쪽 열까지 dfs를 탐색하면서 처음에는 방문배열을 이용했으나

한 지점에서 맨 오른쪽 열까지 갈 수 있는 경로의 경우는 체크할 수 있었느나

여러지점에서 경로가 겹치지않고 연결 할 수 있는 최대 파이프 경우의 수를 알기 어려웠다.

백트래킹을 배웠기때문에 이와 관련하여 생각해본결과 이미 한 파이프가 연결된다면
flag 를 true 처리하고, dfs내부에서 가지치기하는 부분에 if(flag) return;
을 추가하여 가지치기를 허용하지 않았다.

그리고 지나간 지점은 v 로 바꿔서 방문 체크했다.

package com.day13;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class BOJ3109_빵집 {
	public static char map [][];
	public static int [] dx = {-1,0,1};
	public static int [] dy = {1,1,1}; 
	public static int R , C , answer;
	public static boolean endFlag;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());

		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new char[R][C];
		
		//map 입력받기
		for (int i = 0; i < R; i++) 
			map[i] = br.readLine().toCharArray();
		

		//dfs 호출
		for(int i = 0 ; i < R ; i ++) {
			//시작할때 끝 열은 false 로 초기화
			endFlag = false;
			connectPipe(i,0,0);
		}
		
		/*
		for(int i = 0 ; i < R;  i ++) {
			System.out.println();
			for(int j = 0 ; j < C ; j++)
				System.out.print(map[i][j]);
		}
		*/
			
		
		sb.append(answer);
		System.out.println(sb);
	}

	
	private static void connectPipe(int x, int y, int length) {
		if(length == C-1) {
			//도착한 순간 플래그 체크
			endFlag = true;
			answer++;
			return;
		}

		for(int i = 0 ; i < 3 ; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			//배열 안쪽에 위치 , 다음지점이 . 인경우 , 아직 방문하지 않은 곳
			if(nx>=0 && ny>=0 && nx<R && ny<C && map[nx][ny] == '.') {
				map[x][y] = 'o'; // 해당 점은 방문 체크
				connectPipe(nx,ny, length +1); 
				
				//이번 dfs사이클에서 이미 도착했으면 
				//가지치기 허용하지말고 걍싹다 리턴
				if (endFlag) return;
			}
		}
	}
}