백준(BOJ) 16929번 Two Dots

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

16929번: Two Dots

풀이 :

 

DFS를 통해 사이클이 발견 시 true를 반환하도록 ccheck 함수를 만들었다.

 

이때 by bx는 이전 y,x를 나타내는데 if (ny == by && nx == bx )는 뛰어넘도록 만들어 주었다.

 

by와 bx가 없다면 오른쪽으로 갔다가 바로 왼쪽으로 가는 경우도 사이클로 판단하기 때문이다

 

코드 ( C++ )

	#include <iostream>
	#include <algorithm>
	#include <vector>
	#include <queue>
	#include <tuple>
	using namespace std;
	int n, m;
	char a[51][51];
	bool visited[51][51];
	const int dy[4] = { 1,-1,0,0 };
	const int dx[4] = { 0,0,1,-1 };
	bool ccheck(int i, int j, int by, int bx, char alp)
	{
	if (visited[i][j]) return true;
	visited[i][j] = true;
	bool ret = false;
	for (int k = 0; k < 4; ++k) {
	int ny = i + dy[k];
	int nx = j + dx[k];
	if (!(0 <= ny && ny < n && 0 <= nx && nx < m)) continue;
	if (ny == by && nx == bx) continue;
	if (alp != a[ny][nx]) continue;
	ret +=ccheck(ny, nx, i, j,alp);
	}
	return ret;
	}
	int main()
	{
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < m; ++j)
	cin >> a[i][j];
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < m; ++j) {
	if (visited[i][j]) continue;
	if (ccheck(i, j, -1, -1,a[i][j])) {
	cout << "Yes" << "\n";
	return 0;
	}
	}
	cout << "No" << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub