백준 3109번. 빵집(c++) / Greedy

그리디 문제이다.

가스관에서 빵집으로 가는 특정 경로를 완성하게 되면 그것과 전혀 겹치지 않는 경로를 또 만들어야 하기 때문에

한 번 빵집에 도착했으면, 맨 처음 가스관으로 돌아가서 새로운 경로를 찾아가는 것이 핵심이다.

그래서 dfs에서 빵집에 도착하면 true를 리턴해주어서 계속 처음으로 돌아가게 해주었다.

 

// 빵집
#include <iostream>
using namespace std;
 
int r, c;
string s;
char map[10001][501];
int visited[10001][501] = {0, };
int dx[3] = {-1, 0, 1};
int dy[3] = {1, 1, 1};
int ans = 0;
 
bool dfs(int x, int y)
{
    if(y==c-1){
        ans++;
        return true;
    }
 
    for(int j=0; j<3; j++){
        int nx = x+dx[j];
        int ny = y+dy[j];
        if(0<=nx && nx<r && 0<=ny && ny<c && !visited[nx][ny]){
            if(map[nx][ny]=='x') continue;
            visited[nx][ny] = true;
            if(dfs(nx, ny)) return true;
        }
    }
 
    return false;
}
 
int main()
{
    cin>>r>>c;
    for(int i=0; i<r; i++){
        cin>>s;
        for(int j=0; j<c; j++){
            map[i][j] = s[j];
        }
    }
 
 
    for(int i=0; i<r; i++){
        visited[i][0] = true;
        dfs(i, 0);
    }
 
    cout<<ans<<"\n";
    return 0;
}