[백준] 3109 빵집

 

DFS+ 그리디를 이용해서 풀 수 있다

우선 지나간 길은 지나갈 수 없으므로 길을 지나갈 때 마다 x로 바꿔주자

그리고 우리가 봐야할 방향은 위부터 봐야 아래 남아있는 정점에 대해 이득이다

 

따라서 위부터 아래로 시작점에서 dfs를 돌리며 끝까지 가는지 체크를 해보자!

 

문제의 핵심은 dfs를 조금 변형하는 부분에 있다고 생각한다

내가 만약 x행의 끝부분까지 간다면 true를 리턴해주면 된다!

아니라면 false~~!

 

결국 도착하는 사람들은 true를 통해 갈 수 있다고 답을 알려준다...!

dfs 열공하자

 

소스코드 (C++)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
int n, m;
int dx[3] = { -1,0,1 };
int dy[3] = { 1,1,1 };
 
char map[10010][505];
 
bool inner(int x, int y) {
    return (0 <= x && x < n && 0 <= y && y < m);
}
bool dfs(int x, int y) {
    map[x][y] = 'x';
    if (y == m - 1) return true;
    for (int i = 0; i < 3; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (inner(nx, ny) && map[nx][ny] == '.') {
            if (dfs(nx, ny)) return true;
        }
    }
    return false;
}
int main() {
    scanf(" %d %d", &n, &m);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf(" %1c", &map[i][j]);
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) ans += dfs(i, 0);
    printf("%d\n", ans);
}