[백준-3109] 빵집

단순한 그래프 탐색을 진행하게 되면 바로 시간이 터지게 된다.

오른쪽위 → 오른쪽 → 오른쪽 아래 순으로 탐색을 하는 그리디 1, 빵집의 가스관 위쪽부터 차례대로 파이프를 연결할 수 있나? 없나? 를 확인하며 파이프를 만드는 방식의 그리디 2 총 2개의 2그리디 방식을 사용해야 한다.

첫 번째 그리디의 경우 어찌저찌 잘 생각할 수 있겠지만, 두 번째 그리디의 경우에는 생각하기 어려워서.. 매우 오랜 시간이 걸린 문제이다.

로직은 다음과 같다.

• 빵집의 가스관 위쪽 부터 dfs 탐색을 돌며 파이프를 만들 수 있는지 확인한다.
• ( 만들 수 있으면 response 에 +1, 없으면 +0 을 해준다. )

그리디만 알면 생각보다 간단한 문제이나 생각하기 힘들다... 

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long LL;

int n, m;
char arr[10001][501];
int check[10001][501];
int dx[] = { -1,0, 1 };
int dy[] = { 1, 1, 1 };
int _max = 0;
vector<pii> pla;

bool dfs(int x, int y) {
    check[x][y] = 1;
    if (y == m) return true;
    for (int i = 0; i < 3; i++) {
        int cx = x + dx[i];
        int cy = y + dy[i];

        if (cx < 1 || cx > n || cy < 1 || cy > m) continue;
        if (check[cx][cy] || arr[cx][cy] == 'x') continue;

        bool flag = dfs(cx, cy);
        if (flag) return true;
    }
    return false;

}
int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf(" %1c", &arr[i][j]);
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i++) {
        res += dfs(i, 1);
    }

    cout << res;

    return 0;
}

https://www.acmicpc.net/problem/3109

3109번: 빵집