문과 코린이의 IT 기록장] C++ 백준 문제풀이[그래프 1] - Two Dots (16929)

문과 코린이의 IT 기록장] C++ 백준 문제풀이[그래프 1] - Two Dots (16929)

문과 코린이의 IT 기록장] C++ 백준 문제풀이[그래프 1] - Two Dots (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

---

[ 코드 ]

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

/* 이 문제를 dfs로 풀어야 하는 이유
1. 같은 색깔 내에서도 시작점이 어디냐에 따라 사이클 가능 여부가 달라진다.
- bfs로 풀면 시작점을 다르게 해서 일일이 검사를 해야한다
- dfs로 풀면 어디서 시작하든 이동횟수는 일정하게 증가하므로, 그 차이만 계산하면 된다.
 * 인접한 노드를 먼저 방문하는 것(BFS)보다, 하나의 노드를 계속 방문하는 방식(DFS)가 더 적합.

2. 최소거리를 계산하는게 아니라, 가능 여부만 구하는 것이다,
*/

char a[51][51]; // 게임판의 상태 입력 (색깔 입력)
int d[51][51];
bool check[51][51]; // 거쳐온 부분인지 check

int n, m; // 게임판의 크기 n,m (n : 세로, m : 가로)

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

bool bfs(int x, int y, int cnt, char color) {
	if (check[x][y]) // 이미 거쳐온 경우 (check가 true인 경우)
	{
		// 사이클 형성 조건
		if (cnt - d[x][y] >= 4) // 현재까지 진행해온 횟수 - check를 변환했을 때의 횟수 >= 4
		{
			return true; // true 반환
		}
		else
		{
			return false;
		}
	}

	// 거쳐오지 않은 경우 (check가 false인 경우)
	check[x][y] = true;
	d[x][y] = cnt; // 방문하게 되는 시작점의 d배열에, 현재 cnt를 저장한다.

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

		if (0 <= nx && nx < n && 0 <= ny && ny < m)
		{
			if (a[nx][ny] == color)
			{
				if (bfs(nx, ny, cnt + 1, color)) // 이전에 true로 반환되었다면
				{
					return true; // 마지막까지 이 함수가 실행된다면, return true로 마무리
				}
			}
		}
	}

	return false; // 함수가 실행이 안되었다면, return false로 마무리
}

int main() {
	cin >> n >> m; 

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	for (int i = 0; i < n; i++)
	{
		for (int k = 0; k < m; k++)
		{
			if (check[i][k]) // dfs로 진행했기 때문에, 이미 같은 색깔은 다 확인한 것
			{
				continue;
			}

			memset(d, 0, sizeof(d));
		
			bool ok = bfs(i, k, 1, a[i][k]);

			if (ok)
			{
				cout << "Yes" << '\n';
				return 0;
			}
		}
	}

	cout << "No" << '\n';

	return 0;

}