[C++] 백준 3109: 빵집

문제 이해

- 첫째 열: 근처 빵집의 가스관

- 마지막 열: 원웅이의 빵집

- 파이프는 그러므로 첫째 열에서 시작하여 마지막 열에서 끝나야 함

- 파이프의 방향은 우측 위, 우측, 우측 아래만 가능

- 각 칸을 지나는 파이프는 1개만 존재할 수 있다.

 

<조건>

- 시간 제한: 1초

- 메모리 제한: 256MB

 

<입력>

- R: 행의 개수 (1 ~ 10,000, 10^4)

- C: 열의 개수 (5 ~ 500, 10^2)

 

<출력>

- 원웅이가 설치할 수 있는 가스관과 빵집을 연결하는 파이프라인의 최대 개수

 

문제 풀이

DFS를 써야함은 문제를 보면 알 수 있다.

근처 빵집에서 시작해서 원웅이의 빵집까지 연결해야 하니 말이다.

 

 

그런데 파이프의 최대 개수를 어떻게 구할 수 있을까???

답은 바로 그리디 알고리즘의 적용이다.

 

 

그렇다면 그리디 알고리즘은 어떻게 적용할 수 있을까??

시작하는 행의 위치(위 or 아래)와 탐색 방향을 맞게 설정하면(우측 위부터 우측 아래 or 우측 아래부터 우측 위)

그리디하게 탐색할 수 있다. 

 

 

 

※ 이때 주의할 점은 백트래킹 기법을 쓰는 것이 아니라는 점이다.

1. 이미 파이프가 하나 연결되고 나면

다른 지점에서 시작한 파이프는 그곳을 지나갈 수 없다.

 

2. 또한 혹시나 파이프가 진행되다가 막히더라도,

막힌 지점을 통해서 원웅이의 집까지 도달하는 경우의 수는 없다.

 

그러므로 이미 그리디하게 탐색한 곳은 갈 수 없는 곳으로 인식해도 좋은것이다! 

 

 

그리디 알고리즘의 적용이 문제의 핵심이니만큼 그리디 알고리즘 유형의 문제로 둬도 되지 않나 싶다.

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int r, c, ans = 0;
int map[10005][505];
int dy[3] = {-1, 0, 1};
int dx[3] = {1, 1, 1};

bool dfs(int y, int x){
    if(x == c-1){
        ans++;
        return true;
    }

    map[y][x] = 1;

    for(int i = 0; i < 3; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny >= 0 && ny < r && nx >= 0 && nx < c && map[ny][nx] == 0){
            if(dfs(ny, nx)) return true;
        }
    }

    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>r>>c;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            char tmp;
            cin>>tmp;
            if(tmp == '.') map[i][j] = 0;
            else map[i][j] = 1;
        }
    }

    for(int i = 0; i < r; i++){
        dfs(i, 0);
    }

    cout<<ans;
    return 0;
}