[Baekjoon,3109] 빵집

초기에 모든 경로를 DFS를 이용하며 만들었고 다음 두 가지의 경우에 따라 방문 여부를 표시했다.

• 경로를 완성한 경우 : 방문해온 지점을 표시한다.
• 경로 완성을 실패한 경우 : 방문해온 표시를 해제한다.

이러한 방법은 이전에 실패했던 경로를 다시 방문하여 총 $R$개의 출발 지점에 대해 시간복잡도가 $O(R\times 3^C)$로 시간초과가 난다.
그런데 방금 말했듯이 DP처럼 이전에 시도하다 실패한 지점을 다시 방문하지 않으면 해결할 수 있지 않을까? 어짜피 다시 이곳을 다른 경로를 통해 방문한다고 해도 실패할 것이 뻔하기 때문이다. 이는 경로 완성을 실패한 지점 또한 다시 방문 하지 않도록 하여 구현할 수 있다.

구현

이에 대한 구현을 아래에서 볼 수 있다. 추가적으로 시작, 도착 파이프 라인 위치에 한 칸씩 띄어 탐색을 하고 있는 것을 볼 수 있다. 파이프 라인을 한 칸 띄운다고 해도 충분히 도달 가능하기 때문이다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int dy[3]={-1,0,1};

int r,c;
vector<string> board;
bool visited[10000][500];

// 범위를 확인한다. 
inline bool inRange(int y, int x)
{
    return 0<=y && y<r && 0<=x && x<c;
}

bool dfs(int y, int x)
{
    if(visited[y][x] || board[y][x]=='x')
        return false;
    visited[y][x]=true;
    // 경로가 완성된 경우 
    if(x==c-2)
        return true;
    
    // 세 가지 방향에 대해 탐색한다. 
    for(int i=0;i<3;++i)
    {
        int ny=y+dy[i];
        int nx=x+1;
        // 하나라도 완성되면 바로 반환한다. 
        if(inRange(ny,nx) && dfs(ny,nx))
            return true;
    }
    // 표시를 해제하지 않는다!!
    // visited[y][x]=false;
    return false;
}

int solve()
{
    int ret=0;
    memset(visited,false,sizeof(visited));
    // 모든 출발 지점에서 탐색을 시작한다. 
    for(int i=0;i<r;++i)
        if(board[i][1]=='.')
            ret+=dfs(i,1);
    
    return ret;
}

int main()
{
    cin>>r>>c;
    board=vector<string>(r);
    for(int i=0;i<r;++i)
        cin>>board[i];
    
    cout<<solve()<<endl;
    
    return 0;
}