[2823] 유턴 싫어

문제: https://www.acmicpc.net/problem/2823

행과 열, 빌딩과 길이 주어졌을 때 유턴을 하지 않고 모든 길을 지나면서 

다시 시작 위치로 올수 있는지를 물어보는 문제이다.

간단하게 DFS를 이용해서 풀었다.

DFS로 갈수 있는 길을 모두 확인하면서

만약 현재 길에서 세 방면 이상이 막혀(빌딩이나 지도의 끝)있다면 이 길은 막다른 길이라고 판단 할 수 있다.

길은 모두 이어져 있다고 문제에 명시되어 있으므로 DFS는 한 번만 수행하면 된다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, res;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int arr[11][11];
int visit[11][11];
int val[11][11];
void dfs(int x, int y){
    visit[x][y] = 1;
    for(int i=0; i<4; i++){
        int nx = dx[i] + x;
        int ny = dy[i] + y;
        if(visit[nx][ny]) continue;
        if(nx>=0 && ny>=0 && nx<n && ny<m && !arr[nx][ny])
            dfs(nx, ny);
        else
            val[x][y] += 1;
    }
}
int main(){
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            char ltr;
            scanf(" %1c", &ltr);
            if(ltr == 'X')    arr[i][j] = 1;
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(arr[i][j] == 0 && !visit[i][j]){
                dfs(i, j);
                break;
            }
        }
    }
 
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(val[i][j] >= 3){
                puts("1");
                return 0;
            }
        }
    }
    puts("0");
    return 0;
}