[백준 3109] 빵집

[백준 3109] 빵집

문제 링크

#include "header.h"
using namespace std;
int R, C, answer;
// 오른쪽 위 대각선, 오른쪽, 오른쪽 아래 대각선
int dx[3] = { -1, 0, 1 };
int dy[3] = { 1, 1, 1, };
char market[10001][501];
int visit[10001][501];
bool ans;
//'.'는 빈 칸이고, 'x'는 건물
void input(){
    cin >> R >> C;
    for(int i=0; i<R; i++){
        for(int j=0; j<C; j++){
            cin >> market[i][j];
        }
    }
}
void dfs(int x, int y){
    visit[x][y] = 1;
    
    //기저 조건
    //오른쪽 끝에 도달함
    if(y == C-1){
        ans = true;
        answer++;
        return;
    }

    //아니라면 대각선 탐색
    for(int i=0; i<3; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(visit[nx][ny] || market[nx][ny] == 'x' || nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
        
        dfs(nx, ny);
        if(ans) return;
    }

}
void solve(){

    for(int i=0; i<R; i++){
        ans = false;
        dfs(i, 0);
    }

}
int main()
{
    input();
    solve();

    cout << answer << endl;

    return 0;
}

• 처음에는 끝에 도달 했을 시에, 다음 dfs를 바로 돌렸는데, 그렇게 하니 무한 루프가 돌았다.

• 방문 처리를 해주고, dfs 처리 후, 다시 방문 처리를 없앴는데, 중복으로 방문을 하다 보니 무한 루프가 돈 것 같다.

• 오른쪽으로 이동 할 시에, 오른쪽 상단, 오른쪽, 오른쪽 아래 순으로 탐색을 하면 경로가 막히지 않는다.
• 최단 경로가 보장이 되기 때문에 방문처리를 철회할 필요도 없다.
• R만큼 돌면서 dfs를 돌린다.
• 끝에 방문 시에는 더이상 탐색 할 필요가 없으므로 flag를 두어 return을 하고, 다음 인덱스 dfs를 돌린다.