알고리즘 :: 백준 :: DFS :: 16929 :: Two Dots

문제

게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구해보자.

문제접근

• 사이클의 존재 여부를 확인하는 문제다.
  오일러 사이클(트레일) 문제인줄 알고 겁먹었지만, DFS만으로 풀 수 있었다.
• 임의의 시작점으로부터 DFS 순회를 시작해서 다시 출발지점으로 돌아올 수 있다면 사이클이 존재한다고 판단할 수 있다.
• 문제에도 언급됐지만, "사이클을 이루는 최소 구성요소는 4개"다. 그러므로 이 문제는 다음 두 가지 방법으로 풀 수 있다.
  1. 이미 방문한 정점을 다시 방문했을 때, 출발 정점으로부터 거리가 4 이상이면 사이클이 있다고 판단한다.
  2. 이전에 방문한 정점을 기록하면서 전진할 때, 이미 방문한 정점을 다시 방문했을 때, 사이클이 있다고 판단한다.
  • 위 두 방법 모두 글로 봐서는 이해가 쉽지 않으므로 그림으로 설명해보자.

• [첫 번째 방법]
  • 좌측 그림을 보자.
  • 출발지로부터 재방문지점은 거리가 1이다.
  • 재방문지점을 가리키는 파란 정점은 DFS 함수로 따지면, 출발지로부터 5번째 호출된 지점이며 이는 곧 거리가 5임을 의미한다.
  • 즉, 두 거리의 차가 4 이상이므로 사이클을 이룸을 알 수 있다.
• [두 번째 방법]
  • 우측 그림을 보자.
  • 이전에 방문한 정점을 기록하기 때문에 상하좌우 이동 시 방금 방문했던 정점으로 다시 돌아갈 일은 없다.
  • 출발지에서 재방문지점으로 갔을 때, 재방문지점에서 다시 출발지로 가는 사이클은 존재하지 않는다. (사이클 최소 구성요소 4개 규칙 위배 X)
  • 그러므로, 이전에 방문한 정점을 다시 방문했을 때, 사이클이 만들어짐을 알 수 있다.
• 여기서는 두 번째 방법을 이용해서 풀이했으며 두 방법의 코드 차이는 거의 없다.

코드

#include <iostream>
#include <cstring>
using namespace std;

static int N, M;
static char map[51][51];
static bool isVisited[51][51];
static constexpr int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

inline bool isPossible(int y, int x) {
	return (0 <= y && y < N) && (0 <= x && x < M);
}

bool solve(int y, int x, int py, int px) {
	if (isVisited[y][x]) return true;	// 사이클이 형성됐다면 true를 반환한다.
	isVisited[y][x] = true;		// 방문 표시한다.
	for (int i = 0; i < 4; ++i) {	// 상하좌우 네 방향에 대해 탐색한다.
		int ny = y + d[i][0], nx = x + d[i][1];
		// 1) 범위 내에 있는 점이고, 2) 이전에 방문한 점이 아니며, 3) 같은 색상이라면 전진.
		if (isPossible(ny, nx) && !(ny == py && nx == px) && map[ny][nx] == map[y][x])
			if (solve(ny, nx, y, x)) return true;
	}
	return false;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N >> M;
	for (int i = 0; i < N; ++i) cin >> map[i];	// char 배열 입력은 이렇게도 받을 수 있다!
	
	for (int y = 0; y < N; ++y)
		for (int x = 0; x < M; ++x) {		// 모든 점에 대해 DFS를 수행한다.
			if (isVisited[y][x]) continue;	// 이미 방문한 점이라면 DFS 수행 불필요.
			memset(isVisited, false, sizeof(isVisited));
			if (solve(y, x, y, x)) {
				cout << "Yes\n";
				return 0;
			}
		}
	cout << "No\n";
	return 0;
}

결과