[DFS] 백준 16929 - Two Dots

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

16929번: Two Dots

문제

Two Dots는 Playdots, Inc.에서 만든 게임이다. 게임의 기초 단계는 크기가 N×M인 게임판 위에서 진행된다.

각각의 칸은 색이 칠해진 공이 하나씩 있다. 이 게임의 핵심은 같은 색으로 이루어진 사이클을 찾는 것이다.

점 k개 d1, d2, ..., dk로 이루어진 사이클의 정의는 아래와 같다.

• 모든 k개의 점은 서로 다르다. 
• k는 4보다 크거나 같다.
• 모든 점의 색은 같다.
• 모든 1 ≤ i ≤ k-1에 대해서, di와 di+1은 인접하다. 또, dk와 d1도 인접해야 한다. 두 점이 인접하다는 것은 각각의 점이 들어있는 칸이 변을 공유한다는 의미이다.

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

입력

첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문자 한 글자이다.

출력

사이클이 존재하는 경우에는 "Yes", 없는 경우에는 "No"를 출력한다.

 

제한

• 2 ≤ N, M ≤ 50

예제 입력 1 

3 4
AAAA
ABCA
AAAA

예제 출력 1 

Yes

 

 

---

보자마자 dfs 생각이 났다. 모든 출발점을 검색하고, dfs의 깊이가 4이상인 상태에서 출발점으로 돌아오는 상황이 생긴다면 사이클이 존재한다고 판단할 수 있다.

 

• 점의 색이 같아야 이어질 수 있다.

나는 모든 출발점을 dfs로 확인할 것이다. 그러나, 만약 dfs로 방문했던 곳이라면 출발점으로 정의하고 검색해볼 필요가 없다. 그 점과 이어진 점과는 사이클이 없다는 증명이니까.

그러니까, 출발점을 돌릴 때 그 출발점의 색을 전역변수로 두고 dfs는 그 색이 갈을 때만 함수를 재귀적으로 호출하게 하면 된다.

 

만약 모든 점을 확인했는데도 "yes"판정이 나오지 않았다면, "no"를 출력하게 했다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

#define SIZE 51
#define endl '\n'

using namespace std;

int N, M; // 게임판의 크기. 세로, 가로
string dots[SIZE]; // 입력된 도트들
int visited[SIZE][SIZE]; // 방문여부 체크

int startH, startW; // 검색시작한 위치
char startColor; // 시작위치의 색

int moveHigh[4] = { -1, 0, 1, 0 };
int moveWidth[4] = { 0, 1, 0, -1 };

void dfs(int high, int width, int depth) // 찾을 집, 깊이
{
	if (startH == high && startW == width && depth >= 4) // 사이클 완성
	{
		cout << "Yes" << endl;
		exit(0);
	}
	for (int i = 0; i < 4; ++i)
	{
		int nextH = high + moveHigh[i];
		int nextW = width + moveWidth[i];

		if (nextH >= N || nextH < 0 || nextW >= M || nextW < 0)
			continue;

		if (!visited[nextH][nextW] && dots[nextH][nextW] == startColor) // 방문한 적 없고, 같은 색일 때
		{
			visited[nextH][nextW] = true;
			dfs(nextH, nextW, depth + 1);
			visited[nextH][nextW] = false;
		}
	}
}
int main()
{
	cin >> N >> M;

	for (int i = 0; i < N; ++i)
	{
		string temp;
		cin >> temp;

		dots[i] = temp;
	}

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			if (!visited[i][j]) // 방문한적 없는 칸
			{
				//visited[i][j] = true;
				startH = i; startW = j;
				startColor = dots[i][j];
				dfs(i, j, 0);
			}
		}
	}
	cout << "No" << endl;
}