[알고리즘] 백준3109 빵집 - 자바

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

3109번: 빵집

 

[풀이 코드]

package day0217;

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

public class BOJ_3109_빵집 {
	static int R, C, cnt;
	static char[][] graph;
	static boolean[][] visited;
	static int[] dy = {-1, 0, 1};
	static int[] dx = {1, 1, 1};
	static boolean flag; // 스택에 쌓여있는 재귀들을 처리해주기 위함
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		graph = new char[R][C];
		visited = new boolean[R][C];
		for(int r=0; r<R; r++) {
			String str = br.readLine();
			for(int c=0; c<C; c++) {
				graph[r][c] = str.charAt(c);
			}
		}//그래프 담기
		
		for(int i=0; i<R; i++) {
			flag = false; // 스택에 쌓여있는 재귀처리를 위한 변수
			dfs(i, 0);
		}
		
		System.out.println(cnt);
	}
	
	static void dfs(int y, int x) {
		if(x==C-1) { // 끝에 도달했다면
			flag = true; // true로 변경하고 쌓였있던 재귀함수들 다 return시키기
			cnt++; 
			return;
		}
		
		for(int d=0; d<3; d++) {//오른쪽위, 오른쪽, 오른쪽아래 순서
			int yy = y + dy[d];
			int xx = x + dx[d];
			if(yy>=0 && xx>=0 && yy<R && xx<C) { //범위초과하지 않았다면
				if(!visited[yy][xx] && graph[yy][xx] == '.') { // 방문한적 없고 이동가능한 경우라면
					visited[yy][xx] = true; // 방문처리
					dfs(yy, xx); // 이동
					if(flag) return; // 쌓여있던 스택을 처리해주기 위함
				}
			}
		}//for종료
	}
	
}

• 스택에 쌓여있는 재귀를 처리해주는 게 중요했던 문제였다. 처음에는 그냥 끝에 닿았으면 return 하거나 다음 for문이 실행 안되게끔 break를 걸면 되지 않을까 생각했었다.
  
  
• 메인 문에서 for문을 통해 출발지점 순서대로 dfs문을 실행시키기 전에 flag변수를 false로 초기화하고 시작한다. 
  
  
• 그림과 같이 스택에는  dfs(1,3)가 dfs(0, 4)를 방문하고 dfs(1,4), dfs(2,4)를 방문하려고 하겠지만 이미 (0, 4)에서 파이프 하나를 생성했기 때문에 dfs(1, 4), dfs(2, 4)를 방문하면 안 됐다.
  - 이 부분에서 막혔고 이를 처리하기 위해서 flag를 변수를 두어 (0, 4)에 도달했다면 true를 저장하고 쌓여있던 dfs(1, 3)에게 true면 return 시키도록 했다. 그럼 dfs(1, 4), dfs(2,4)를 방문하지 않고 연쇄적으로 스택에 쌓여있던 재귀 함수들은 종료될 것이다.
  
  
• 위 그림이 예제의 확실한 정답인지 모르겠지만 빨간색은 연결되면 안 되는 파이프이고 파란색이 파이프가 연결된 선이다.