[백준 3109] 빵집 C++

3109번: 빵집

이 문제는 그리디 알고리즘을 적용한 DFS문제이다

 

그리디를 어떻게 적용하는가??

• 항상 오른쪽 위 부터 탐색을 해야한다(0번째 Row부터 탐색할 경우만 해당. R-1번째 부터 탐색하면 오른쪽 아래부터 탐색)
• 탐색을 한 부분은 다시 탐색하지 않는다! (DP개념도 같이 적용)

문제를 이해했다면 항상 오른쪽 위 부터 탐색해 간다는건 쉽게 이해할 수 있다

나도 처음엔 이것만 생각해서 백트래킹 방식을 적용해 37 번 라인에 방문했던 곳을 초기화 해주는 코드(Map[r][c] = 0;)가 있었다.

하지만 Map[r][c] = 0; 을 넣어주게되면 방문 기록이 초기화 되기 때문에

바로 다음 row에서 시작하는 dfs를 시작했을 때, 이전 row에서 탐색했던 곳들도 중복해서 또 탐색하게 된다.

그래서 첫 시도는 시간초과가 발생했다.. 당연히 O(r * 3^c) 이니까.. 시간초과

 

생각을 좀 더 해보니 한 번 방문 했던 곳은 다시 갈 필요가 없었다

 

• A라는 점을 거쳐서 간 곳이 원웅이집에 도달 했으면 cnt에 1이 더해질 것이고 true를 리턴한다.
• 현재까지 지나온 길은 원웅이 집에 도달 한 경우이므로 dfs를 되돌아가며 다른 길로 새지 않고, 방문했던 점을 남겨두면서 시작점으로 돌아간다
• 다른 집에 막혀서 도달하지 못했다 하더라도 A점을 거치면 어차피 도달하지 못하므로 cnt를 카운팅해주지 않고 방문한 점들을 남겨두면서 시작점으로 돌아간다

그래서 46번 line 의 for문을 돌면서 다음 dfs가 실행될 때는 이전에 탐색했던 점들을 알고있는 상태로 시작하기 때문에 시간이 매우 절약되게되고, 결과적으로 O(RC) 시간복잡도를 얻게 된다!

 

그래프탐색을 베이스로 그리디, dp개념이 조금씩 들어가있는 재미있는 문제였다

 

#include <iostream>
 
using namespace std;
 
int R, C, cnt = 0;
int Map[10001][501];
int dr[3] = {-1, 0, 1};
int dc[3] = {1, 1, 1};
 
void input(){
    string in;
    cin >> R >> C;
    for(int i = 0; i < R; i++){
        cin >> in;
        for(int j = 0; j < C; j++){
            if(in[j] == '.') Map[i][j] = 0;
            else Map[i][j] = 1;
        }
    }
}
 
bool DFS(int r, int c){
    if(c == C-1){
        cnt++;
        return true;
    }
    
    Map[r][c] = 1;
    
    for(int i = 0; i < 3; i++){
        int nr = r + dr[i];
        int nc = c + dc[i];
        if(nr >= 0 && nr < R && nc >= 0 && nc < C && !Map[nr][nc]){
            if(DFS(nr, nc)) return true;
        }
    }
    
    return false;
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    input();// 0번 열에서 아래로 내려가면서 dfs실행
    for(int i = 0; i < R; i++){
        DFS(i, 0);
    }
    cout << cnt;
    
    return 0;
}