BOJ 3109. 빵집

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include<cstdio>

#define MAX_R 10010
#define MAX_C 505

int R, C;
char board[MAX_R][MAX_C];

bool backtracking(int r, int c) {
	if\(r < 0 \|| r >= R \|| board\[r]\[c] == 'x')
		return false;	

	board[r][c] = 'x';

	// 마지막 col에 도달하면 종료
	if(c >= C-1)
		return true;

	int nc = c + 1;

	/* 
	   오른쪽 위 대각선, 오른쪽, 오른쪽 아래 대각선 3곳 중 한 곳만 갈 수 있어도 통과
	   그 중 무조건 오른쪽 위 대각선부터 방문해야 최댓값이 나올 수 있으므로 위쪽부터 방문하고,
	   그 결과가 true라면 오른쪽이나 오른쪽 아래 대각선으로 가는 경우는 할 필요가 없음.
	   오른쪽 위 대각선의 결과가 false라서 오른쪽을 방문할 경우일 때에도 마찬가지로 
	   오른쪽의 결과가 true이면 오른쪽 아래 대각선으로 갈 필요가 없음.
	 */
	return backtracking\(r-1, nc) \|| backtracking\(r, nc) \|| backtracking\(r+1, nc);
}

int main() {
	scanf("%d %d\n", &R, &C);
	for(int i = 0; i < R; i++)
		scanf("%s", board[i]);

	int res = 0;
	// Row 한 줄씩 backtracking을 수행
	for(int i = 0; i < R; i++)
		res += backtracking(i, 0);

	printf("%d\n", res);
}