빵집

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

public class B3109 {
	static int r, c, ans, dx[] = {-1, 0, 1};
	static char[][] B;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		B = new char[r][c];
		for (int i = 0; i < r; i++) {
			char[] tmp = br.readLine().toCharArray();
			for (int j = 0; j < c; j++) {
				B[i][j] = tmp[j];
			}
		}
		
		ans = 0;
		for (int i = 0; i < r; i++) {
			if (dfs(i, 0)) ans++;
		}
		
		bw.write(String.valueOf(ans));
		bw.flush();
		bw.close();
		br.close();
	}

	private static boolean dfs(int x, int y) {
		if (y == c-1) return true;
		B[x][y] = '-';
		for (int d = 0; d < 3; d++) {
			int nx = x + dx[d];
			int ny = y + 1;
			if (nx >= 0 && nx < r && B[nx][ny] == '.') {
				if (dfs(nx, ny)) return true;
			}
		}
		return false;
	}
}

---

G2

놓을 수 있는 파이프라인의 경우의 수 가 아니다.
놓을 수 있는 파이프라인의 최대 개수 이다.

이게 그리디를 생각해낼 수 있는 포인트다.

만약 전자라면, R*(3^C) 이다.
=> 열에서 각 행의 위치당 3가지 탐색을 하고 열을 끝까지 이동하는 모든 경우의 수.

이러면 어떻게 연산을 해도 무리다.

하지만 놓을 수 있는 최대 개수라면, 방향을 오른쪽 위, 오른쪽, 오른쪽 아래 이런 식으로 정해놓고 탐색을 진행하면 된다.

** Why?) 제일 위 행부터 아래쪽으로 탐색을 하는데, 위에서 출발한 파이프라인이 필드를 가로질러 버리면 그게 아래쪽 탐색에서의 최선이 아니기 때문이다. (파이프라인은 서로 겹칠 수 없기 때문)

즉, 위에서 부터 탐색을 하고, 길이 있다면 최대한 위쪽 길을 찾아 몰아 넣는 느낌으로 진행하는 것이다.

절대적으로 그리디 라는 검증하는 것은 쉽지 않을 수 있다.
사실 풀기 전에 이 방법이 그리디가 된다는 확신은 없었다.

하지만 위쪽으로 몰아넣고 순차적으로 재귀를 타는 이 방법이 가장 최선처럼 보였고, 이런 가능성이 보였다면 시도해 보는 것이 맞는 것 같다.

---

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