백준 3109 / c++ / 그리디 / dfs

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

이 문제는 그리드를 이용한 dfs이다 즉 dfs의 탐색방향을 그리디를 통해 정해주게 되는것이다 우리는 오른쪽 부터 왼쪽으로 파이프를 순서대로 연결할건데 이때 파이프는 오른쪽 ,오른쪽 아래 ,왼쪽 아래 이렇게 만 움직일수있는데 우리가 오른쪽부터 파이프를 놓는데 진행중에 왼쪽 방향으로 탐색을 진행하게되면 파이프가 쭉 왼쪽으로 가면서 다른애들의 연결을 막게된다 왼쪽부터 탐색할거면 반대로 놓아도 되긴 한다

#include<iostream>
using namespace std;
int R, C;
int arr[10001][501];
int cnt = 0;
int dr[3] = { -1, 0, 1 };
int dc[3] = { 1, 1, 1 };
bool canGo(int r, int c) {
	if (!arr[r][c] && r >= 0 && r < R && c >= 0 && c < C)
		return true;
	else
		return false;
}
bool dfs(int r, int c) {
	if (c== C - 1) {
		cnt += 1;
		return true;
	}
	else {
		arr[r][c] = 1;
		for (int i = 0; i < 3; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];
			if (canGo(nr, nc)) {
				if (dfs(nr, nc)) {
					return true;
				}
			}
		}
		return false;
	}
}
int main() {
	cin >> R >> C;
	string inputStr;
	for (int i = 0; i < R; i++) {
		cin >> inputStr;
		for (int j = 0; j < C; j++) {
			if (inputStr[j] == '.')
				arr[i][j] = 0;
			else
				arr[i][j] = 1;
		}
	}

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

	cout << cnt;
	return 0;
}