[JAVA] 백준 3109 빵집 풀이

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

3109번: 빵집

---

풀이 방법

1. DFS로 시작부분부터 탐색한다.

2. 끝까지 갔는데 최종 y좌표가 C-1과 같다면, 파이프라인이 설치된 것 => 다른 탐색 필요없음, 파이프라인 생성 여부 저장

3. 다른 탐색을 하기 위해 되돌아갈 때, 파이프라인 생성 여부가 true라면 방문 표시하고 return

 

틀렸던 부분 & 주의할 부분

1. 좌표를 방문할 때마다 방문 표시를 해줬는데 이렇게 하니 실패한 파이프라인의 방문 표시를 false로 다시 만드는게 번거로웠음 -> 한턴 다 끝나고 나서 돌아갈 때 방문표시를 해줌

2. 탐색의 순서를 오른쪽 대각선 위-오른쪽-오른쪽 대각선 아래로 해야 최적의 경로 찾을 수 있음

3. 실패한 파이프라인의 경로를 표시해두면, 다음 좌표가 (i,0) 가 탐색하지 않기 때문에 시간을 줄일 수 있음 

 

Java 최종 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_3109_빵집 {
	static int R,C;
	static char[][] map;
	static int cnt; // 총 경우의 수
	static StringTokenizer st;
	// 오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래
	// 이동 순서 중요
	static int[][] dir= {{-1,1},{0,1},{1,1}}; 
	static boolean[][] visited;
	static boolean flag;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		st=new StringTokenizer(br.readLine());
		R= Integer.parseInt(st.nextToken());
		C= Integer.parseInt(st.nextToken());
		
		map=new char[R][C];
		visited=new boolean[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;
			dfs(i,0);
		}
		System.out.println(cnt);
	}
	private static void dfs(int r,int c) {
		if (c==C-1) {
			cnt++;
			flag=true; // 파이프라인 완성했을 경우
			visited[r][c]=true;
			return;
		}
		
		for (int d=0; d<3; d++) {
			int dr=r+dir[d][0];
			int dc=c+dir[d][1];
			if(isOkay(dr,dc) && visited[dr][dc]==false&& map[dr][dc]=='.') {
				dfs(dr, dc);
				if (flag) {
					// 하나 완성했을때, 방문했던 곳 표시, 다른곳 탐색할 필요x
					visited[r][c]=true; 
					return;
				}else {
					// 완성하지 못했을 경우, 안되는 경로 표시
					visited[r][c]=true; 
				}
			}
		}
	}
	
	// 범위 확인
	private static boolean isOkay(int r, int c) {
		return r>=0 && c>=0 && r<R && c<C;
	}
}

아직 재귀가 익숙하지 않은 것 같다. 한턴 끝나고 나서 조건 주는 방식이 아직 익숙하지 않은 것 같다. 

쫌더 연습 해야겠다..