[백준] 3109번 빵집

3109 빵집 

문제

---

빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다.

원웅이는 가스관과 빵집을 연결하는 파이프를 설치하려고 한다. 빵집과 가스관 사이에는 건물이 있을 수도 있다. 건물이 있는 경우에는 파이프를 놓을 수 없다.

가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 한다. 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있고, 각 칸의 중심끼리 연결하는 것이다.

원웅이는 가스를 되도록 많이 훔치려고 한다. 따라서, 가스관과 빵집을 연결하는 파이프라인을 여러 개 설치할 것이다. 이 경로는 겹칠 수 없고, 서로 접할 수도 없다. 즉, 각 칸을 지나는 파이프는 하나이어야 한다.

원웅이 빵집의 모습이 주어졌을 때, 원웅이가 설치할 수 있는 가스관과 빵집을 연결하는 파이프라인의 최대 개수를 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 R과 C가 주어진다. (1 ≤ R ≤ 10,000, 5 ≤ C ≤ 500)

다음 R개 줄에는 빵집 근처의 모습이 주어진다. '.'는 빈 칸이고, 'x'는 건물이다. 처음과 마지막 열은 항상 비어있다.

출력

---

첫째 줄에 원웅이가 놓을 수 있는 파이프라인의 최대 개수를 출력한다.

---

풀이)

얼떨결에 맞은 문제이다.

dfs를 이용해서 첫번째의 열의 첫번째 행에서 마지막 행까지 각자 출발해

마지막열에 도착하면 파이프라인 개수를 늘려주었다.

아무래도 i행과 아래 행들인  i+1, i+2 ...행들의 경로가 최대한 겹치면 안되니깐

파이프 연결방법을 아래와 같은 우선순위 순으로 연결했다. 

① 오른쪽 대각선 위 ／

② 오른쪽 ―

③ 오른쪽 대각선 아래 ＼

이런 순으로 탐색하니 정답이 나왔다.

→풀고나서 보니 그리디 문제였다.

  위와 같은 순서로 탐색한다는 자체를 그리디로 보나 보다.

코드)

#include <stdio.h>
#include <queue>
using namespace std;
 
int r, c;
char map[10000][500];
int dy[3] = { -1,0,1 };
int dx[3] = { 1,1,1 };
bool visited[10000][500];
int result;
bool check = false;
void dfs(int y,int x) {
    if (check) return;
    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) {
            if (visited[ny][nx] || map[ny][nx] == 'x') continue;
            visited[ny][nx] = true;
            if (nx == c - 1) {
                result++;
                check = true;
                return;
            }
            dfs(ny, nx);
            if (check)return;
        }
    }
}
 
int main() {
    scanf("%d %d", &r, &c);
    getchar();
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            scanf("%c", &map[i][j]);
        }
        getchar();
    }
    for (int i = 0; i < r; i++) {
        dfs(i, 0);
        check = false;
    }
    printf("%d", result);
    return 0;
}

결과)