[백준 3109] 빵집

DFS만 쓰면 시간초과가 난다

따라서 DP로 못가는 경로는 미리 막아두어 다음턴에도 해당 경로로 탐색이 불가능하게 해줘야한다

 

이미 지나간 경로도 map[newy][newx] = 1 로 마킹하고 길이 없는 경로도 1로 마킹되게 해서 접근하지 못하게 하였다.

---

#include <iostream>
#include <bitset>

using namespace std;

int R, C;

bitset<501> map[10001];

// 오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래 순서로
int dy[3] = {-1, 0, 1};
int dx[3] = {1, 1, 1};

int dfs(int cury, int curx){
    // 종점 도달이면
    if (curx == C - 1)
    {
        map[cury][curx] = 1;
        return 1;
    }

    int newy, newx;
    for (int i = 0; i < 3; i++)
    {
        newy = cury + dy[i];
        newx = curx + dx[i];

        // 범위 넘어가면
        if (newy < 0 || newx < 0 || newy >= R || newx >= C)
            continue;

        // 건물이거나 이미 지나간 곳이면
        if (map[newy][newx] == 1)
            continue;

        // 종점까지 간게 성공했으면 경로 마킹
        if(dfs(newy, newx)) {
            map[newy][newx] = 1;
            return 1;
        }
    }

    // 못가는 경로는 1로 막기
    map[newy][newx] = 1;
    return 0;
}

void solve(){
    queue<pair<int, int>> q;

    // 시작점 추가 + 방문처리
    for (int i = 0; i < R; i++)
    {
        if(map[i][0]==0) {
            q.push(make_pair(i, 0));
            map[i][0] = 1;
        }
    }

    int ans = 0;
    int cury, curx, newy, newx;
    while (!q.empty())
    {
        cury = q.front().first;
        curx = q.front().second;
        q.pop();

        // 도착했으면 해당 건은 종료
        if(curx == C-1){
            ans++;
            continue;
        }

        for (int i = 0; i < 3; i++)
        {
            newy = cury + dy[i];
            newx = curx + dx[i];

            // 범위 넘어가면
            if(newy < 0 || newx < 0 || newy >= R || newx >= C)
                continue;

            // 건물이거나 이미 지나간 곳이면
            if(map[newy][newx]==1)
                continue;

            map[newy][newx] = 1;
            q.push(make_pair(newy, newx));
            break;
        }
    }

    cout << ans;
}

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

    cin >> R >> C;
    char ch;
    for (int i = 0; i < R; i++)
    {
        for (int k = 0; k < C;k++){
            cin >> ch;
            if(ch=='x') map[i][k] = 1;
        }
    }

    // solve();

    int ans = 0;

    // 시작점 추가 + 방문처리
    for (int i = 0; i < R; i++)
    {
        if (map[i][0] == 0)
        {
            ans += dfs(i, 0);
        }
    }

    cout << ans;

    return 0;
}