[백준] 16929번 : Two Dots

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

16929번: Two Dots

---

//C++

#include <bits/stdc++.h>
#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi 3.1415926535
using namespace std;
typedef long long ll;
char arr[51][51];
int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
int visited[51][51];
int n, m;
bool go(int x, int y, int px, int py, char color)
{
	if (visited[x][y] == 1) //mark 1
		return true;
	visited[x][y] = 1;

	for (int i = 0; i < 4; i++)
	{
		int nx = x + dir[i][0];
		int ny = y + dir[i][1];
		if ((nx != px) || (ny != py))
		{
			if ((arr[nx][ny] == color) && (nx >= 0 && nx < n && ny >= 0 && ny < m))
			{
				if(go(nx, ny, x, y, color)) return true;
			}
		}
	}
	return false;
}
int main() {

	F_I;

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			cin >> arr[i][j];
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (visited[i][j]) //mark 2
				continue;
			if (go(i,j, 0,0, arr[i][j]))
			{
				cout << "Yes" << '\n';
				return 0;
			}
		}
	}
	cout << "No" << '\n';
}

> 방문을 할 때의 방문 조건!

 

1. 방문하는 점들의 색깔이 같아야 하고(애초에 같은 색깔 끼리 사이클을 이루어야 하니까) ((arr[nx][ny] == color))

2. 방문하는 점들이 범위 안에 있어야 하고 ((nx >= 0 && nx < n && ny >= 0 && ny < m))

3. 또한 '서로 다른' 점들을 하나씩 방문해야 한다. ((nx != px) || (ny != py))

 

이 3가지 조건을 모두 만족하면서 dfs 로 방문을 하다가, 이미 방문한 적이 있는 점을 만났다는 것은(위 소스코드의 mark 1 부분), 다시 말해서 사이클이 존재한다는 의미이므로, true 를 return 한다. 

 

윗 부분을 그림으로 표현한 것

---

> main문에서는 이중 반복문을 통해 입력된 점을 모두 한번씩 돌면서 (물론, 여기서는 이미 방문한 점을 가지고 또 함수 호출을 하면 안된다. 소스코드의 mark 2 부분), go 함수를 호출했을 때, return 값이 true인게 하나라도 있다면, 사이클이 최소 1개 이상 존재한다는 의미이므로, 그때는 Yes를 출력하고 바로 프로그램 종료를 한다.

 모든 점을 다 돌았음에도 불구하고 true를 한번이라도 return 받지 못했다면, 사이클이 하나도 없다는 의미이므로, No를 출력하고 프로그램을 종료한다.