[BOJ] 3109 빵집

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

3109번: 빵집

 

처음에는 dfs로 풀지 않고 반복문을 돌렸다.

열을 먼저 탐색하면서 오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래를 방문할 수 있는지 없는지 확인하고 방문할 수 있다면 check표시를 해주고 check표시가 된 경우에만 탐색을 할 수 있도록 구현하였는데 틀렸다. 반례가 있는거 같은데 못찾겠어서 그냥 모든 열 마다 dfs를 돌렸다. 

 

dfs를 돌릴 때 한 번 방문한 점은 다시 방문할 필요가 없다는 것을 주의해야 한다.

 

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>

#define endl '\n'
#define ll long long

using namespace std;

char map_[10000][500];
bool visit[10000][500];
int R,C;

int d[]={-1,0,1};

void input() {
    cin>>R>>C;
    for(int i=0;i<R;i++)
        for(int j=0;j<C;j++){
            cin>>map_[i][j];
            //if(map_[i][j]=='x') check[i][j]=-1;
        }
}

void init() {
    //for(int i=0;i<R;i++) check[i][0]=1;
}

bool dfs(int i,int j){
    if(j==C-1) return true;
    
    for(int y=0;y<3;y++){
        int ny=i+d[y],nx=j+1;
        if(0<=ny&&ny<R&&map_[ny][nx]=='.'&&!visit[ny][nx]){
            visit[ny][nx]=true;
            bool flag=dfs(ny,nx);
            
            if(flag) return flag;
        }
    }
    return false;
}


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

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    cout<<solution();
    return 0;
}