[BOJ]백준 3019번: 빵집(C++)/Greedy

처음에 풀었던 코드

#include <cstdio>
#define INF 987654321
char map[10005][10005];
bool visit[10005][10005];
int n, m, ans,dx[] = { 1,1,1 }, dy[] = { -1,0,1 },k=INF,col[10005];
bool safe(int r, int c) { return r >= 0 && r < n && c >= 0 && c < m; }
bool pipe(int r,int c) {
	if (c == m-1) {
		visit[r][c] = true;
		return true;
	}
	for (int i = 0; i < 3; i++) {
		int nr = r + dy[i], nc = c + dx[i];
		if (!safe(nr,nc)||map[nr][nc] == 'x'||visit[nr][nc])continue;
		visit[r][c] = true;
		if (pipe(nr, nc)) {
			return true;
		}
	}
	return false;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf(" %s", map[i]);
		for (int j = 0; j < m; j++) {
			if (map[i][j] == '.')col[j]++;
		}
	}
	for (int j = 0; j < m; j++) {
		if (col[j] < k)k = col[j];
	}
	for (int i = 0; i < n; i++) {
		if (ans >= k)break;
		if (pipe(i, 0))ans++;
	}
	printf("%d", ans);
	return 0;
}

최적화를 거친 코드

#include <cstdio>
char map[10005][505];
int n, m, ans;
bool pipe(int r,int c) {
	if (map[r][c]!='.')return false;
	if (c == m-1) return true;
	map[r][c] = 'x';
	return pipe(r - 1, c + 1) || pipe(r, c + 1) || pipe(r + 1, c + 1);
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf(" %s", map[i]);
	}
	for (int i = 0; i < n; i++) {
		if (pipe(i, 0))ans++;
	}
	printf("%d", ans);
	return 0;
}