2823 유턴 싫어

DFS / BFS로 풀어서 자기자신 돌아오면 된다는 건 감을 잡았는데 유턴 조건 때문에 막혔다. 그래서 재귀로 할까 생각했는데 공식도 모르겠고. 알고보니 전에 벽 부수는 문제처럼 상태값 저장해서 풀어야 했다. 하지만... 하지만..... 너무 어려웠다. 머리로는 이해되는데 코드로 안 나옴. 특히 이전 방향 저장하고 이후 방향 비교하는 게 어렵스.. 넘 어렵스.. 

 

이틀 고민하다가 포기! 북님 코드 보고 어떻게 돌아가는지 확인해야겠다.

 

다음 문제로 넘어감

 

아 뭐야 이거 쉬운 문제였다.. 

 

 

유턴하지 않는다만 집중하면 된다.

사진처럼 길이 있을 때 길이 한 방향만 있다면 막힌 길이라 유턴을 해야 한다. 그래서 자기 옆에 길이 몇 개만 있는지 확인하면 된다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

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

int     main()
{
    int n, m;
    scanf("%d %d", &n, &m);

    vector<string> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (v[i][j] == '.')
            {
                int cnt = 0;

                for (int k = 0; k < 4; k++)
                {
                    int nx = i + dx[k];
                    int ny = j + dy[k];

                    if (nx < 0 || n <= nx || ny < 0 || m <= ny)
                        continue;

                    if (v[nx][ny] == '.')
                        cnt++;
                }

                if (cnt <= 1)
                {
                    printf("1\n");
                    return 0;
                }
            }
        }
    }
    printf("0\n");
    return 0;
}