[백준] 3109번: 빵집 - java

나의 풀이

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

public class Main {

	static int r, c;
	static char arr[][];
	static int pipe;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		arr = new char[r][c];
		for (int i = 0; i < r; i++) {
			arr[i] = br.readLine().toCharArray();
		}

		for (int i = 0; i < r; i++) {
			if (dfs(i, 0)) {
				pipe++;
			}
		}
		System.out.println(pipe);

	}

	static boolean dfs(int row, int col) {

		arr[row][col] = 'o'; // 방문 표시

		if (col == c - 1) { // 마지막 열에 도착한 것
			return true;
		}

		if (row > 0 && arr[row - 1][col + 1] == '.') {// 오른쪽위대각선
			if (dfs(row - 1, col + 1))
				return true;
		}
		if (arr[row][col + 1] == '.') {// 오른쪽
			if (dfs(row, col + 1))
				return true;
		}
		if (row + 1 < r && arr[row + 1][col + 1] == '.') {// 대각선 아래
			if (dfs(row + 1, col + 1))
				return true;
		} 

		return false;
	}


}

 

* 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있다.

따라서 i행 0열부터 시작하여 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 가는 3가지 경우를 DFS로 탐색한다.

 

1) 기저조건

마지막 열에 도착했다면 0~마지막열까지 파이프라인을 모두 설치했음을 뜻하므로 true 를 리턴하며 종료한다.

2) 방문표시

dfs 문을 돌면서 현재 row, col 에 방문표시를 한다.

처음에는 만약 DFS 로 마지막 열까지 도달하지 못한 경우에는 다시 방문 표시를 원상복귀해야하는 것 아닌가? 하고 생각했다.

그러나 다시 생각해본다면, 하지 않아야 함을 알 수 있다.

왜냐하면 DFS 에 성공한 경우, 실패한 경우 모두 다시 탐색할 필요가 없기 때문이다!!!!!

1) 만약 DFS에 성공한 경우 => 이미 다른 파이프가 설치된 경우이므로 방문 표시 필요

2) 만약 DFS에 실패한 경우 => 다른 case에서 해당 row,col 에서  DFS 탐색을 진행할 경우 실패함을 뜻한다. 따라서 다른 경우에서 실패가 보장된 좌표를 다시 탐색하지 않도록 하는 것이다.

 

 

3) 탐색

오른쪽 위 대각선 -> 오른쪽 -> 오른쪽 아래 대각선 순서대로 탐색해야 한다. 왜냐하면 최대한 많은 파이프라인을 연결해야 하므로, 파이프가 밑 행으로 내려오는 것 보다 위에 존재해야 더 많은 공간이 확보되기 때문이다. 

 

즉, 만약 오른쪽 위 대각선에서 마지막 열까지 도달할 수 있다면, 오른쪽과 오른쪽아래대각선은 굳이 탐색하지 않아도 이미 최적의 해가 구해졌음을 뜻하는 것이다.

=> 따라서 아래와 같이 dfs() 문이 true 를 리턴하는 경우에는 return true 를 하여, 가지치기를 방지해야 한다.