[Java] 백준 3109번: 빵집

[문제 바로 가기] - 빵집

📌 유형 : DFS + 그리디

💡 아이디어

가스관과 빵집을 연결하는 파이프라인의 최대 개수를 구하려면 시작점과 도착점의 순서가 중요하다. 무슨 뜻이냐면 시작점을 오름차순으로 탐색한다면, 도착점도 최대한 오름차순으로 도착하도록 해야한다는 뜻이다.

나는 열을 0부터 R-1순으로 탐색을 했으므로 파이프라인을 오른쪽 위 -> 오른쪽 -> 오른쪽 아래 순으로 탐색했다. (오른쪽 아래를 먼저 탐색하고 싶다면 열을 R-1부터 0까지 탐색하면 된다.)

	public static int[][] deltas = {{-1, 1}, {0, 1}, {1, 1}};

	for (int i = 0; i < R; i++) {
		dfs(i, 0);
	}

최적의 해를 찾아 탐색하였으므로 visited[dx][dy]는 false 처리해주지 않아도 된다.

또한 이미 하나의 파이프라인이 완성되었을 경우에는 해당 경로를 선택할 수 없기 때문에 flag를 사용해서 true일 경우에는 return만 해주었다.
이 부분은 다른 사람의 풀이를 보니 1. 파이프라인 설치 가능할 경우 dfs 함수 true 반환 2. 불가능일 경우 false 반환하여 처리해줘도 괜찮았을 것 같다.

풀이

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

/**
 * 백준 3109번 빵집
 * - DFS + 그리디
 */
 
public class Main {
	public static int R, C, result = 0;
	public static int[][] deltas = {{-1, 1}, {0, 1}, {1, 1}}; // 오른쪽 위부터 탐색해야 함
	public static char[][] map;
	public static boolean[][] visited;
	public 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());
		
		map = new char[R][C];
		for (int i = 0; i < R; i++) {
			String s = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = s.charAt(j); 
			}
		}
		
		visited = new boolean[R][C];
		for (int i = 0; i < R; i++) {
			flag = false;
			dfs(i, 0);
		}
		
		System.out.println(result);
	}
	
	public static void dfs(int x, int y) {
		if (y == C - 1) {
			result++;
			flag = true;
			return;
		}
		
		for (int i = 0; i < 3; i++) {
			int dx = x + deltas[i][0];
			int dy = y + deltas[i][1];
			
			if (dx < 0 || dy < 0 || dx >= R || dy >= C || visited[dx][dy] || map[dx][dy] == 'x') continue;
			
			if (flag) return;
			else visited[dx][dy] = true;
			
			dfs(dx, dy);
		}
	}
}