취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 16929번 문제인 Two Dots이다.
문제는 아래 링크를 확인하자.

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

문제에서 주어진 게임판을 각 칸을 노드, 상하좌우의 같은 색의 연결된 칸들끼리의 연결관계를 에지로 하는 그래프로 생각하자. 문제에서 찾는 사이클은 위의 그래프에서 사이클을 찾는 것과 같다.

dfs 트리를 만드는 과정에서 부모 노드가 아닌 이미 지나왔던 점을 다시 탐색하게 된다는 것은 그 경로를 이을 시 사이클이 생긴다는 것과 같으므로, 이를 이용하여 탐색을 하면 사이클의 존재 여부를 간단히 판단할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int R, C;
string board[50];
bool visited[50][50];

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

bool dfs(int curr, int curc, int parr, int parc, char letter) {
	bool ret = 0;
	visited[curr][curc] = 1;
	for (int i = 0; i < 4; i++) {
		int r = curr + dr[i], c = curc + dc[i];
		if (r < 0 || r >= R || c < 0 || c >= C) continue;
		if (r == parr && c == parc) continue;
		if (board[r][c] != letter) continue;
		if (visited[r][c]) return 1;
		if (dfs(r, c, curr, curc, letter)) return 1;
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> R >> C;
	for (int r = 0; r < R; r++) cin >> board[r];

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (visited[r][c]) continue;
			if (dfs(r, c, -1, -1, board[r][c])) {
				cout << "Yes";
				return 0;
			}
		}
	}

	cout << "No";
}