[C++] 백준 2823번 유턴 싫어

유턴을 하지 않고 마을 전부를 돌아다닐 수 있는지 찾는 문제입니다.
(x, y)에서 유턴을 하지않고 (x, y)로 돌아 올 수 있어야하며,
다시 나갈 수도 있어야합니다.

한 지점에서 2방향이 싸이클을 돌고 돌아올 수 있으면
그 지점은 문제가 없는 지점으로 판단하였습니다.
그리고 싸이클을 돌고 돌아온 경로들 모두 문제가 없다고 판단 해주었습니다.
1방향만 돌아오거나, 못돌아오는 경우 유턴이 불가능 한것으로 간주했습니다.

DFS를 사용했고 visit를 통해서 같은 곳을 무한루프 되는 것을 막았습니다.
역주행에 대해서는 왔는 방향의 좌표를 기억해서 그 좌표로는 이동 못하게 하였습니다.
문제가 없는 곳일 경우 visit에 기록된 곳들을 전부 clear배열에 넣어두었습니다.
clear배열은 문제가 없는 곳들로 탐색을 하지 않습니다.

 

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

int n, m;
bool clear[20][20];
char map[20][20];
int visit[20][20];
int moveX[4] = { 0, 1, 0, -1 };
int moveY[4] = { 1, 0, -1, 0 };

void copy()
{
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (visit[i][j] > 0) {
				clear[i][j] = true;
			}
		}
	}
}

bool DFS(int a, int b, int sy, int sx, int py, int px) 
{
	if (clear[a][b] || (a == sy && b == sx && visit[a][b] == 1)) {
		return true;
	}
	for (int i = 0; i < 4; ++i) {
		int x = b + moveX[i];
		int y = a + moveY[i];

		if (map[y][x] != '.' || visit[y][x] == 2 || (x == px && y == py)) {
			continue;
		}

		++visit[y][x];
		if (DFS(y, x, sy, sx, a, b)) {
			return true;
		}
		--visit[y][x];
	}

	return false;
}

int main(int argc, char* argv[])
{
	int c;
	string s;

	memset(map, ' ', sizeof(map));
	memset(clear, false, sizeof(clear));

	cin >> n >> m;

	for (int i = 1; i <= n; ++i) {
		cin >> s;
		for (int j = 1; j <= m; ++j) {
			map[i][j] = s[j - 1];
		}
	}

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (map[i][j] != '.') {
				continue;
			}

			c = 0;
			for (int k = 0; k < 4; ++k) {
				int x = j + moveX[k];
				int y = i + moveY[k];

				if (map[y][x] != '.') {
					continue;
				}

				memset(visit, 0, sizeof(visit));
				
				if (clear[i][j]) {
					++c;
					continue;
				}

				if (DFS(i, j, i, j, i, j)) {
					++c;

					if (c > 1) {
						copy();
						break;
					}
				}
			}
			if (c < 2) {
				cout << "1" << endl;
				return 0;
			}
		}
	}

	printf("0\n");

	return 0;
}