백준 16929번 Two Dots // C++

문제

 

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"를 출력한다.

 

---

 

풀이

 

같은 문자로 이루어진 싸이클이 있는지 확인하면 되는 문제이다.

 

DFS를 통하여 싸이클을 조사하였는데, 싸이클의 경우 처음 좌표와 마지막 좌표가 같아야 한다.

 

이 때, 다음과 같은 경우는 싸이클이 안 되기 때문에 예외 처리를 해주었다.

 

 

1번에서 2번으로 간 뒤, 다시 1번으로 가는 경우는 싸이클이 아니기 때문에 다른 점으로 가면서 이전 점으로 돌아가지 않게 어느 방향에서 왔는지를 함수의 인자로 넘겨주었다.

---

 

코드

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

void input();
void solve();
void dfs(int startX, int startY, int curX, int curY, int prevDir);
int nextDir(int curDir);

char ch[51][51];
int visit[51][51] = { 0, };
int N, M;
int dir[4][2] = { {0,1}, {0,-1}, {1,0}, {-1,0} };
bool finish = false;

int main() {
	input();
	solve();

	if (finish) {
		cout << "Yes" << "\n";
	}
	else {
		cout << "No" << "\n";
	}

	return 0;
}

void input() {
	cin >> N >> M;

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

void solve() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			dfs(j, i, j, i, -1);

			memset(visit, false, sizeof(visit));

			if (finish)
				return;
		}
	}
}

void dfs(int startX, int startY, int curX, int curY, int prevDir) {
	if (startX == curX && startY == curY && visit[startY][startX]) {
		finish = true;
		return;
	}

	if (finish)
		return;

	for (int i = 0; i < 4; i++) {
		if (i == prevDir)
			continue;

		int nextX = curX + dir[i][0];
		int nextY = curY + dir[i][1];

		if (0 <= nextX && nextX < M && 0 <= nextY && nextY < N) {
			if (!visit[nextY][nextX] && ch[startY][startX] == ch[nextY][nextX]) {
				visit[nextY][nextX] = true;
				dfs(startX, startY, nextX, nextY, nextDir(i));
			}
		}
	}
}

int nextDir(int curDir) {
	switch (curDir) {
	case 0:
		return 1;
	case 1:
		return 0;
	case 2:
		return 3;
	case 3:
		return 2;
	}
}