BOJ)3109 빵집

문제: icpc.me/3109

맨 왼쪽부터 맨 오른쪽 까지 중복되지 않는 최대 경로의 개수를 구하는 문제이다.

우리는 x->y로 가는 경로가 있을 경우 무조건 오른쪽으로만 이동가능하므로 h라는 지점에서 갈 수 있는 길이없다면 다시 h를 밟아도 경로가 없다는걸 그리디하게 생각하면 알 수 있다.

이 생각에 기반하여 dfs를 이용하여 갈 수 있는 경우가 나오면 다른 방향을 탐색하지 않는 것으로 경로의 중복을 막아 답을 구해줄 수 있다.

#include <cstdio>
#include <algorithm>
using namespace std;
int r, c, visited[10002][502], res;
char a[10002][502];
int dx[] = { -1,0,1 };
int dy[] = { 1,1,1 };
int dfs(int x, int y) {
    visited[x][y] = 1;
    if (y == c - 1)return 1;
    for (int i = 0; i < 3; i++) {
        int cx = x + dx[i];
        int cy = y + dy[i];
        if (!visited[cx][cy] && a[cx][cy] == '.') {
            int v = dfs(cx, cy);
            if (v)return v;
        }
    }
    return 0;
}
int main() {
    scanf("%d%d", &r, &c);
    for (int i = 0; i < r; i++) {
        getchar();
        for (int j = 0; j < c; j++)
            scanf("%c", &a[i][j]);
    }
    for (int i = 0; i < r; i++)
        res += dfs(i, 0);
    printf("%d\n", res);
    return 0;
}