[백준] 2668번, 10451번 C++ : 사이클을 이용한 알고리즘 문제 풀이

 

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

 

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

 

 

 

위 두 문제는 '사이클'을 이용하여 풀이를 할 수 있습니다.

 

'사이클'이란 순환하는 그래프 구조를 뜻하며

각 문제에서 사이클을 판단하는 방법이 다릅니다.

 

10451번

 

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int arr[1001];
bool visited[1001];
int Count;

void dfs(int node)
{
	visited[node] = true;
	int next = arr[node];
	if (!visited[next])
	{
		dfs(next);
	}
}

int main()
{
	int T;
	cin >> T;

	while (T--)
	{
		int N;
		cin >> N;

		for (int i = 1; i <= N; i++) cin >> arr[i];

		Count = 0;

		for (int i = 1; i <= N; i++)
		{
			if (!visited[i])
			{
				dfs(i);
				Count++;
			}
		}
		memset(visited, false, sizeof(visited));

		cout << Count << endl;
	}

}

이 문제에서는 사이클을 판단하기 위해 dfs 함수를 다음과 같이 정의합니다.

 

void dfs(int node)
{
	visited[node] = true;
	int next = arr[node];
	if (!visited[next])
	{
		dfs(next);
	}
}

 

이 dfs에서는 현재 node (인덱스)를 받아

해당 node 방문 처리 후

다음 방문할 node가 이전에 방문하지 않았다면

이동하는 방식입니다.

위의 방식대로 진행한다면

 

 

다음과 같은 사이클대로 진행되며

총 3개의 사이클을 찾을 수 있습니다.

이때 예시를 기준으로 1 ~ 8까지 방문을 dfs를 진행하려 할 때

1번 이후 3, 5, 7 노드는 이미 1번 노드가 포함된

사이클 내에 존재하기 때문에

3, 5, 7은 방문처리가 되어 있고 dfs를 진행하지 않습니다.

 

즉, 이전 번호 노드의 사이클에 포함되어 있는

노드들은 dfs를 진행하지 않음으로

사이클 개수를 세지 않습니다.

2668번

#include <iostream>
#include <vector>

using namespace std;

int arr[101];
bool visited[101];
vector<int> ans;

void dfs(int cur, int start)
{
	if (visited[cur])
	{
		if (cur == start)
		{
			ans.push_back(cur);
		}
		return;
	}
	visited[cur] = true;
	dfs(arr[cur], start);
}

int main()
{
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> arr[i];
	}

	for (int i = 1; i <= N; i++)
	{
		memset(visited, false, sizeof(visited));
		dfs(i, i);
	}
	
	cout << ans.size() << endl;
	for (auto x : ans) cout << x << "\n";
}

 

위 경우에는 사이클을 뽑되, 가장 수가 많은 사이클을 뽑는 방식입니다.

 

여기서 이전에 했던 사이클 판단 방식과는 달리

시작 노드와 현재 노드를 비교해야 합니다.

 

 

void dfs(int cur, int start)
{
	if (visited[cur])
	{
		if (cur == start)
		{
			ans.push_back(cur);
		}
		return;
	}
	visited[cur] = true;
	dfs(arr[cur], start);
}

 

이 dfs에서는 현재 노드(cur)와 시작 노드(start)를 받습니다.

만약 현재 노드에 방문을 했을 경우에는

시작 노드와 비교하며

시작 노드 = 현재 노드가 되는 경우에

사이클이 완성되므로 ans 벡터에 정답을 넣어줍니다.

 

이때, cur 노드의 방문 처리를 if 문 이후에 처리하기 때문에

가능한 로직입니다.