[백준 알고리즘/C++/그리디/DFS] 3109 빵집

 

 

제일 왼쪽 열에서 제일 오른쪽 열까지 파이프를 연결하려고 한다

파이프는 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있다

파이프라인의 최대 개수를 구하는 문제!!

 

 

그리디로 접근하는 DFS 문제다 (멍청하게 DFS로 풀 생각 안해서 돌아 돌아 갔음)

 

//DFS

첫번째 열에서 오른쪽으로 한칸씩 이동하며 가장 마지막 열까지 갈 수 있는지 확인해야 한다

//그리디

오른쪽 위 대각선, 아래 대각선, 바로 옆 ← 이렇게 세 가지 경우로 이동할 수 있는데,

위 대각선, 바로 옆, 아래 대각선 순서대로 확인해야 올바른 값을 구할 수 있다

아래부터 가버리면 아래 파이프들을 막게 되니까 최대 개수를 찾을 수 없다

 

main에서 행마다 한번씩 실행하도록 하고,

dfs 함수에서 x == c - 1, 즉 가장 마지막 열까지 가면 count 후 return하면 된다

 

 

#include <iostream>
using namespace std;
 
int r, c;
char arr[10000][500];
bool visited[10000][500] = { false, };
int res = 0;
const int dy[] = { -1,0,1 };
 
bool dfs(int y, int x) {
    visited[y][x] = true;
    if (x == c - 1) {
        res++;
        return true;
    }
 
    for (int i = 0; i < 3; i++) {
        int nx = x + 1;
        int ny = y + dy[i];
 
        if (ny < 0 || ny >= r || visited[ny][nx] || arr[ny][nx] == 'x') continue;
 
        if (dfs(ny, nx)) return true;
    }
 
    return false;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 0; i < r; i++)
        dfs(i, 0);
 
    cout << res;
}

 

nx는 무조건 +1 이니까 dx[]는 따로 안만들었음