[백준] 3109. 빵집

---

풀이

DFS를 통해 탐색을 진행할 때 최대값을 찾는 경우는 대부분 모든 경우의 수를 확인해야 하기 때문에 유망하지 않은 경우 가지치기하는 백트래킹 방법을 사용할 수 없다. 하지만 이 문제는 시작 점은 가장 위에서부터 연결할 수 있는 경우에는 연결하는 경우가 최선의 방법이 되는 그리디한 접근 방식을 사용하였고 이를 통해 유망하지 않은 경우 탐색을 종료하는 경우 되돌아가는 백트래킹 방식을 사용하였다.  

첫번쨰 열의 1번쨰 행부터 탐색을 진행하고, 만약 C번째 행에 도착했다면 이번 시작 위치에서의 탐색을 종료한다. 다음 위치도 동일하게 진행하는데 만약 실패한다고 하더라도 방문한 위치에 대한 체크를 되돌리지 않는다. 왜냐하면 해당 위치에서 파이프를 완성하지 못했다고 하더라도 뒤 선택지에서 해당 방향은 동일하게 실패하는 경우가 되기 때문이다.

그리고 중요한 부분은 탐색의 순서가 위 => 중간 => 아래 순서로 진행되어야지만 최선의 경우를 찾게 된다는 부분이다.

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

public class Solution3109 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static char[][] map;
	static boolean[][] check;
	static int R, C, cnt, max = Integer.MIN_VALUE;
	static boolean isReached;

	public static void main(String[] args) throws IOException {
		String[] input = br.readLine().split(" ");
		R = Integer.parseInt(input[0]);
		C = Integer.parseInt(input[1]);
		map = new char[R][C];
		check = new boolean[R][C];

		for (int i = 0; i < R; i++) {
			char[] line = br.readLine().toCharArray();
			for (int j = 0; j < C; j++) {
				map[i][j] = line[j];
			}
		}
	
		for (int i = 0; i < R; i++) {
			if (isReached) continue;
			isReached = false;
			buildPipe(i, 0);
			if (isReached) {
				isReached = false;
				cnt++;
			}
		}
		System.out.println(cnt);
	}

static void buildPipe(int row, int col) {

	if (col == C - 1) {
		isReached = true;
		return;
	}

	check[row][col] = true;
	if (isvalid(row - 1, col + 1) && !isReached)
		buildPipe(row - 1, col + 1);
	if (isvalid(row, col + 1) && !isReached)
		buildPipe(row, col + 1);
	if (isvalid(row + 1, col + 1) && !isReached)
		buildPipe(row + 1, col + 1);
}

	static boolean isvalid(int row, int col) {
		if (row < 0 || row >= R || map[row][col] == 'x' || check[row][col])
			return false;
		return true;
	}
}