[백준] 3109 - 빵집

BFS로 풀려다가 메모리초과랑 런타임이 오지게 난 문제

원래 아이디어는 BFS로 탐색 후 도착하면 그 경로를 역추적하여 마킹하는 과정을 전부 돌아봐주는 방법

map과 큐, check와 경로를 저장하는 배열까지 만들었으니 메모리가 초과날만 한듯

DFS로 풀기 두려웠던 것은 시간초과가 날 것 같다는 생각에 BFS로 했던 것인데 메모리라니...

결국 DFS로 풀었다

1. 시작점을 돌면서 DFS 탐색 시작

2. 갈 수 있는 위치면 체크하고 들어간다

3. 도착했다면 리턴하며 1을 반환

#include <iostream>
#include <memory.h>
#define MX 10005
using namespace std;
 
char map[MX][503];
int check[MX][503];
int dx[] = { 1, 1, 1 };
int dy[] = { -1, 0, 1 };
int R, C, dab;
 
int dfs(int x, int y)
{
    map[y][x] = 'x';
    if (x == C - 1) return 1;
    for (int i = 0; i < 3; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= C || ny >= R || map[ny][nx] == 'x') continue;
        if (dfs(nx, ny)) return 1;
    }
    return 0;
}
 
int main(void)
{
    cin >> R >> C;
    for (int i = 0; i < R; i++)
        cin >> map[i];
    for (int i = 0; i < R; i++)
        dab += dfs(0, i);
    cout << dab << '\n';
    return 0;
}