[BOJ]16929번: Two Dots (c++)

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

16929번: Two Dots

 

방법 1: 이동 횟수를 저장하며 탐색

#include <iostream>
#include <vector>

using namespace std;

int dir_x[4] = {0, 1, 0, -1};
int dir_y[4] = {1, 0, -1, 0};
int N, M;

// 깊이 우선 탐색
bool dfs(vector<string> &map, vector<vector<int>> &check, int x, int y)
{
	// 4방향 탐색
	for (int i = 0; i < 4; ++i)
	{
		int new_x = x + dir_x[i];
		int new_y = y + dir_y[i];

		// 불가능한 위치일 때
		if (new_x < 0 || new_x >= N || new_y < 0 || new_y >= M)
		{
			continue;
		}

		// 색이 같을 때
		if (map[x][y] == map[new_x][new_y])
		{
			// 아직 방문하지 않은 위치일 때, 
			// 이동횟수를 현재 이동횟수 + 1 저장 후 dfs 재귀호출
			if (check[new_x][new_y] == 0)
			{
				check[new_x][new_y] = check[x][y] + 1;
				// 한번이라도 사이클이 가능하면 true반환 후 종료
				if (dfs(map, check, new_x, new_y))
				{
					return true;
				}
			}
			// 이전에 방문했던 위치일 때, 현재 이동횟수와 적어도 3이상 차이나면 true반환
			else if (check[new_x][new_y] - check[x][y] >= 3)
			{
				return true;
			}
		}
	}
	return false;
}

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

	// 입력
	cin >> N >> M;
	vector<string> map(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> map[i];
	}

	// 이동 횟수를 저장할 int 벡터
	vector<vector<int>> check(N, vector<int>(M));

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			// 아직 방문하지 않은 위치라면
			if (check[i][j] == 0)
			{
				// 방문횟수를 1로 저장 
				check[i][j] = 1;
				
				// dfs로 사이클이 만들어지는지 여부 검사
				if (dfs(map, check, i, j)) 
				{
					cout << "Yes";
					return 0;
				}
			}
		}
	}

	cout << "No";

	return 0;
}

 

방법 2: 사이클 가능 여부만 검사

#include <iostream>
#include <vector>

using namespace std;

int dir_x[4] = { 0, 1, 0, -1 };
int dir_y[4] = { 1, 0, -1, 0 };
int N, M;

/*
	최소 4개의 노드로 된 사이클이 만들어지기만 하면 된다.
	
	2차례 전의 노드와 다른 노드일 때만 방문할 수 있게 했을 때
	전에 방문했던 노드를 다시 방문하게 된다면 
	사이클이 가능한 경우이다. 
*/
bool dfs(vector<string>& map, vector<vector<bool>>& check, pair<int, int> now, pair<int, int> before)
{
	// 전에 방문한 위치일 때 true반환 및 종료
	if (check[now.first][now.second])
	{
		return true;
	}

	// 현재 위치 방문 체크
	check[now.first][now.second] = true;

	// 4방향 탐색
	for (int i = 0; i < 4; ++i)
	{
		int new_x = now.first + dir_x[i];
		int new_y = now.second + dir_y[i];

		// 불가능한 위치일 때
		if (new_x < 0 || new_x >= N || new_y < 0 || new_y >= M)
		{
			continue;
		}

		// 색이 같을 때
		if (map[now.first][now.second] == map[new_x][new_y])
		{
			// 새 지점이 이전 지점과 다를 때
			if (!(new_x == before.first && new_y == before.second))
			{
				// 한번이라도 사이클이 가능하면 true반환 후 종료
				if (dfs(map, check, { new_x, new_y }, now))
				{
					return true;
				}
			}
		}
	}
	return false;
}

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

	// 입력
	cin >> N >> M;
	vector<string> map(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> map[i];
	}

	// 방문여부를 체크할 bool 벡터
	vector<vector<bool>> check(N, vector<bool>(M));

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			// 아직 방문하지 않았다면
			if (!check[i][j])
			{
				// dfs로 사이클이 만들어지는지 여부 검사
				if (dfs(map, check, { i, j }, { -1, -1 }))
				{
					cout << "Yes";
					return 0;
				}
			}
		}
	}

	cout << "No";

	return 0;
}

 

 

방법 2가 공간 효율이 더 좋다.

 

이 문제를 dfs로 풀어야 하는 이유는 다음과 같다.

1. 같은 색깔 무리에서도 시작점이 어디냐에 따라서 사이클 가능 여부가 달라진다.

이때 bfs로 풀면 시작점을 다르게 해서 일일이 검사를 해야 한다. 

dfs로 풀면 어디서 시작하든 이동횟수는 일정하게 증가하므로, 그 차이만 계산하면 된다.

 

 2. 최소 거리를 구하는 게 아니라, 가능 여부만 구하는 것이다.