티스토리 뷰

알고리즘 관련/BOJ

BOJ)3109 빵집

JASON 자손9319 2017. 4. 21. 03:11

문제: icpc.me/3109


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


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


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


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
#include <cstdio>
#include <algorithm>
using namespace std;
int r, c, visited[10002][502], res;
char a[10002][502];
int dx[] = { -1,0,};
int dy[] = { 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;
}
 
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)2610 회의준비  (0) 2017.04.24
BOJ)5913 준규와 사과  (0) 2017.04.21
BOJ)3109 빵집  (0) 2017.04.21
BOJ)1251 단어 나누기  (0) 2017.04.20
BOJ)14503 로봇 청소기  (0) 2017.04.17
BOJ)14500 테트로미노  (4) 2017.04.17
TAG
댓글
댓글쓰기 폼