[백준] 3109번 빵집

[풀이]

이 문제는 DFS를 활용해서 Greedy 하게 풀 수 있는 문제입니다.

DFS를 활용한다는 건 점을 하나하나 이어가면서 x면 되돌아오는 식으로 하는 것으로 쉽게 이해할 수 있는데,

여기서 가장 중요한게 Greedy 부분입니다.

만약 DFS만 활용했을 경우에는

20 20 

..................x.

..................x.

..................x.

  (중략...)

....................

 

이런 입력에 대해서 시간초과가 나오게 됩니다.

x가 끝쪽에 있으니 거의 모든 경우의 경로를 다 돌아보게 되기 때문입니다.

그렇기 때문에 Greedy를 활용해 주어야 합니다. 

이미 실패한 경로는 다시 가더라도 어짜피 결과는 FAIL 입니다.

그러므로 성공한 경로든 실패한 경로든 전부 방문한 걸로 치고 다시는 방문하지 않게 하는 것이 Key Point 입니다.

 

아래는 풀이한 코드입니다.

#include <iostream>
using namespace std;
char map[10000][500];
int xpos[] = { -1,0,1 };
int cnt = 0;
bool dfs(int x, int y, int r, int c) {
    if (y == c - 1) {
        cnt++;
        return true;
    }
    for (int i = 0; i < sizeof(xpos) / sizeof(int); i++) {             
        int next_x = x + xpos[i];
        int next_y = y + 1;
        if (next_y < c && next_x >= 0 && next_x < r) {
            if (map[next_x][next_y] != 'x') {
                bool result = dfs(next_x, next_y, r, c);
 
                // 결과에 상관없이 방문했다는 의미로 'x'표를 해줍니다.
                // 실패했든 성공했든 다시는 그 경로로 갈 일이 없기 때문!!
                map[next_x][next_y] = 'x';
                if (result) return true;
            }
        }
    }
    return false;
}
int main(void) {
    int r, c;
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> map[i][j];
        }
    }
    for(int i=0;i<r;i++)
        dfs(i, 0, r, c);
    cout << cnt;
    return 0;
}

 

질문이나 지적사항은 댓글 부탁드립니다 :)