16929 Two Dots

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

16929번: Two Dots

<개인 풀이>

1. 싸이클이 존재하는지 조건을 파악하는데 힘이들었다. 
(어떻게 싸이클이 있는지 판단할 것인가?)

 -> 같은 '문자'를 방문 할때마다 수를 증가하여, 다시 방문했던 위치의 차를 계산 (예시 1->2->3->4->1)

    1  2  

    4  3 이렇게 1,2,3,4 순으로  (0,0) (0,1) (1,1) (1,0) 으로 방문한경우 마지막으로 이동할 값과, 다시 방문했던 위치의 값   의 차를 계산하였다

  ex) 1->2->3->4 에서 4->다시1로 갈때 현재값 = (4+1) =5(4에서 다음위치이동 값)  - 1(다시방문 지점값) =4;

최소크기가 4이상인 부분은 싸이클이 생성됐다고 판단.

 

2. DFS 재귀 일때 매번 방문마다 거리값을 1증가 해주고, 
   방문 조건은 (좌표 범위내에 있는가? && 다음 문자열도 같은 문자로 이어지는가?)

 주의할 점은, check[xn][yn] == 0 이라는 방문하지 않는 조건을 넣어버리면, 영원히 싸이클을 판단 할 수 없다.

 이유는 다시 방문해야 원점으로 돌아왔을때 검사를 할 수 있으므로.

 

3. 재귀하는 dfs 반환값이 존재하는경우, 재귀할때마다 나오는 반환값과,
    조건에 충족하지 못하는 값들을 가지고, 호출스택을 빠질때마다 true or false를 확인.
    -> 해당 호출스택을 종료와 함께 값 반환,

 

#include<iostream>
#include<cstring>
char mat[60][60];
bool check[60][60];
int dist[60][60];
int n, m;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };

using namespace std;

bool dfs(int x, int y, int cnt, char color);
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	for (unsigned short i = 0; i < n; ++i)
	{
		cin >> mat[i];
	}

	for (unsigned short i = 0; i < n; ++i)
	{
		for (unsigned short k = 0; k < m; ++k)
		{
			//다른 컬러검사시 시작좌표 거리 초기화
			memset(dist, 0, sizeof(dist));
			//각 행,렬 검사
			if (check[i][k] == 0)
			{
				bool isdfs;
				isdfs=dfs(i, k, 1, mat[i][k]);
				if (isdfs)
				{
					cout << "Yes\n" ;
					return 0;
				}
			}
		}
	}
	cout << "No\n";
	return 0;
}

bool dfs(int x, int y, int cnt, char color)
{
	if (check[x][y]) //방문한적이 있다면
	{
		if (cnt - dist[x][y] >= 4) //사이클이 생성 됐다면
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	check[x][y] = true;
	dist[x][y] = cnt;

	for (unsigned short i = 0; i < 4; ++i)
	{
		int xn = x + dx[i];
		int yn = y + dy[i];

		if (xn >= 0 && xn < n && yn >= 0 && yn < m&&
			mat[xn][yn] == color)
		{
			if (dfs(xn, yn, cnt + 1, color))
				return true;	

		}
	}
	return false;

	}