[C++ / 백준 16929번] Two Dots

문제

 

 

해결 방법

문제를 해결하기 전에 해결 방법을 생각해 적어보았다.

사이클 판단 조건 : 사이클은 무조건 4개로 시작한다. 정사각형부터 직사각형까지 여러 형태이다. 하지만 사이클이 있다면 사이클이 크던 작던 시계방향, 반시계방향 둘 중 하나로 무조건 진행 할 수 있으므로 이를 이용해 DFS 로 탐색 시 원래 정점으로 돌아온다면 사이클 이 있는 것이다. 

 

사이클이 있을 시 정점의 개수가 4 이상이어야 하지만 내가 짠 코드에서는 논리 구조상

무조건 원래 위치로 돌아왔을 때(그러려면 자연스레 정점을 4개 를 밟는다) 출력을 해주기 때문에 크게 상관없을 듯 하다.

 

위와 같은 로직으로 (0, 0) ~ (N, M) 까지 bfs 로 전부 순회하며 사이클을 찾았다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <cassert>
using namespace std;

/*
*  사이클 판단 조건 : 사이클은 무조건 4개로 시작한다. 정사각형부터 직사각형까지
* 여러 형태이다. 하지만 사이클이 있다면 사이클이 크던 작던 시계방향, 반시계방향 둘 중 하나로 무조건
* 진행 할 수 있으므로 이를 이용해 DFS 로 탐색 시 원래 정점으로 돌아온다면 사이클
* 이 있는 것이다.
*/

int N, M;

vector<int> v;
char arr[50][50]; 
bool visited[50][50] = { false };
int startX, startY;

bool hasCycle = false;
bool first = true;
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};


void dfs(int y, int x, int prevY, int prevX)
{
	if (first)
	{
		first = false;

	}
	else
	{
		if (x == startX && y == startY)
		{
			hasCycle = true;
			return;
		}
	}
	
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		
		if (nx == prevX && ny == prevY) continue;

		if (nx >= 0 && nx < M  && ny >= 0 && ny < N 
			&& (arr[ny][nx] == arr[y][x] && !visited[ny][nx])
 			)
		{

			visited[ny][nx] = true;
			dfs(ny, nx, y, x);
		}
	}
	return;
}


int main()
{
	cin >> N >> M;

	int j = 0;
	
	getchar();

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			scanf("%1c", &arr[i][j]);
		}
		getchar();
	}

	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < M; x++)
		{
			startY = y;
			startX = x;
			
			dfs(y,x,startY,startX);

			if (hasCycle)
			{
				cout << "Yes";
				return 0;
			}

			fill(&visited[0][0], &visited[49][50], false);
			first = true;
		}
	}

	if(!hasCycle)
		cout << "No";

	return 0;
}