3109 - 빵집

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

3109번: 빵집

생각해보기

1. 이동 가능 방향은 ↗➡↘로 3가지가 있다.
2. 맨 위에서 부터 시작해서 아래로 내려가며 탐색하면 된다.
3. 이미 이동한 곳은 통과가 가능하던 불가능하던 다시 방문할 필요가 없으므로 방문체크를 해주자.

코드

#include<iostream>
#include<string>

using namespace std;

int R,C;
int ans=0;
string pipes[10001];
int my[3]={-1,0,1};

void input(){
    cin>>R>>C;

    for(int i=0;i<R;++i){
        cin>>pipes[i];
    }
}

bool dfs(int y, int x){
    pipes[y][x]='X';
    if(x==C-1){
        ++ans;
        return true;
    }

    for(int i=0;i<3;++i){
        int ny=y+my[i];
        int nx=x+1;
        if(ny<0||ny>=R||pipes[ny][nx]!='.')
            continue;

        if(dfs(ny,nx))
            return true;
    }
    return false;
}

void solution(){
    for(int i=0;i<R;++i){
        dfs(i,0);
    }
    cout<<ans<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    solution();

    return 0;
}