[Algorithm]Baekjoon 3109번 :: 빵집

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

3109번: 빵집

int r, c;
char arr[10001][501];
bool visited[10001][501][3] = { false };
int dir[3][2] = { {-1,1}, {0,1}, {1,1} };
 
int answer = 0;
 
bool DFS(int curY, int curX)
{
    if (curX == c - 1)
    {
        ++answer;
        return true;
    }
 
    for (int i = 0; i < 3; ++i)
    {
        int nextY = curY + dir[i][0];
        int nextX = curX + dir[i][1];
 
        if (nextY < 0 || nextY >= r) continue;
        if (nextX < 0 || nextX >= c) continue;
        if (arr[nextY][nextX] == 'x') continue;
 
        arr[nextY][nextX] = 'x'; 
 
        if (DFS(nextY, nextX))
        {
            return true;
        }
    }
 
    return false; // 끝에 도착못했는데 더이상 갈 수 없다면
}
 
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> r >> c;
 
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 0; i < r; ++i)
    {
        DFS(i, 0);
    }
 
    cout << answer;
 
    return 0;
}

이 문제에서의 핵심은, 3가지방향을 전부 탐색할 필요가 없다는 것이다.

맨 윗행부터 탐색을 시작한다면 최대한 윗쪽방향에 대한 탐색만 수행하면 된다.

갈 수 있는 방향은 총 오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래이다.

만약 여기서 오른쪽 대각선 위로 탐색수행이 가능하다면, 오른쪽이나 오른쪽 대각선 아래로는 갈 필요가 전혀 없다.

처음부터 최대한 윗쪽에 붙여서 탐색하기 때문에 나중에 아랫행에서 탐색을 시작할 때 걸림돌이 될 경우가 없다.

 

그렇게 탐색을 진행하다 끝열을 만나면 카운팅을 해주고 return true를 해주게 되는데, 여기서 또 중요한건 세가지방향이 전부 끝열에 도달하지 못했을 때, 다시 되돌아가면서 방문탐색했던곳을 되돌릴 필요가 없다는것이다.

어차피 현재 특정좌표에서 탐색을 했을 때 끝열에 가는게 실패했다면, 이후 다른 행에서 탐색을 시작하더라도 현재좌표에 온다면 마찬가지로 탐색에 실패하기 때문이다.

 

정리하자면, 처음부터 밑의 행탐색에 영향이 가지않기위해 가장 윗쪽방향먼저 탐색을 수행하게 되는데, 끝열에 도착한다면 더이상의 가지는 치지 않는다. 즉, 만약 끝열에 도착할 수 있는 루트면 그냥 일직선 루트이다.

 

하지만 끝열에 도착하지 못한다면 탐색 가능한대로 계속 가지를 칠 것이고, 친 곳마다 전부 방문탐색을 해줄것이다.

어차피 이후 다른 행에서 해당지점을 가도 결국 끝열에 가지 못하기 때문이다.