[ BOJ 백준 2823 번 - 유턴 싫어 ] 해설 및 코드

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

2823번: 유턴 싫어

 

목적

막다른 길이 있는지 없는지 확인한다.

 

접근법

1. 모든 길을 방문하여 막다른 길이 있는지 없는지 검사한다.

2. 막다른 길이 아니면, 상하좌우 네방향중 2방향 이상으로 이동할 수 있음을 인지한다.

 

#include<iostream>
#define f(a,b) for(int a=0;a<b;++a)
 
using namespace std;
int R, C,cnt;
int d[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
string s[10];
 
bool canMove(int i, int j) {
    if (i == -1 || j == -1 || i == R || j == C|| s[i][j] == 'X')return false;
    return true;
}
 
bool solve() {
    f(i, R)f(j, C)if(s[i][j]=='.') {
        int cnt=0;
        f(k, 4)if (canMove(i + d[k][0], j + d[k][1]))++cnt;
        if (cnt == 1)return false;
    }
    return true;
}
 
int main() {
    cin >> R >> C;
    f(i, R)cin >> s[i];
    cout << (solve() ? 0 : 1)<<endl;
}