[백준/C++] 11724 연결 요소의 개수 (S2)

유형	난이도	완료일	링크	특이사항
DFS/BFS	실버2	23/03/22	https://www.acmicpc.net/problem/11724

 

 

틀린 코드

#include <iostream>

using namespace std;

int arr[1009];

int main(void)
{
	int n, m;
	
	cin >> n >> m;
	
	int cnt = 0;
	
	int v1, v2;
	
	
	for(int i= 0 ; i< m; i++)
	{
		
		cin >> v1 >> v2;
		
		if(arr[v1]==0 && arr[v2]==0) //둘 다 0일 때는 집합 갯수+1 
		{
			cnt++;
			arr[v1] = cnt;
			arr[v2]  = cnt;
		}
		
		else
		{
			if(arr[v1]!=0 && arr[v2]!=0) // 둘 다 0이 아니고
			{
				if(arr[v1]==arr[v2]) //둘이 같을 때는 pass
					continue;
				
				if(arr[v1] < arr[v2])
				{
					cnt --;
					int temp = arr[v2];
					int goal = arr[v1];
					for(int j = 1; j<= n; j++)
					{
						if(arr[j] == temp)
							arr[j] = goal;
					}
				}
				else if(arr[v1] > arr[v2])
				{
					cnt --;
					int temp = arr[v1];
					int goal = arr[v2];
					for(int j =1; j<=n; j++)
					{
						if(arr[j] == temp)
							arr[j] = goal;
					}
				}
			}
			else if(arr[v1] == 0 && arr[v2]!= 0)
			{
				arr[v1] = arr[v2];
			}
			else if(arr[v1]!=0 && arr[v2]==0)
			{
				arr[v2] = arr[v1];
			}
			else
				continue;
		}
		
	}
	for(int i= 1; i<=n; i++)
	{
		if(arr[i]==0)
			cnt++;
	}
	
	cout << cnt;

}

if문으로 모든 경우를 고려했다고 생각했는데 자꾸 2%에서 틀렸다고 해서 고민을 많이 했다. 예제도 이것저것 찾아 넣어봤지만 다 맞게 출력됐다. 그러던 중 자러가기 직전에 cnt로 집합을 구분하는 방식에서 오류가 있을 수 밖에 없다는 것을 발견했다.

두 집합이 합쳐질 때 cnt를 1 감소시키고 새로운 집합이 추가될 때 cnt를 1 증가시킨 후 cnt값을 할당해주는데, 이 때 이미 할당 된 cnt 값을 같은 집합이 아님에도 할당받는 문제가 있었다. 따라서 이렇게 오류가 발생한 두 집합을 합쳐줄 때 cnt 값이 정상적으로 감소하지 않는 문제가 있었다.

너무 큰 결함이고 조금만 깊게 생각해보면 충분히 발견할 수 있었는데 대충 예제만 몇 개 넣어보고 맞다고 논리적으로 완전하게 검증을 거치지 않고 정답이라고 믿은 것 같다. 조금만 복잡한 알고리즘, 논리적으로 조금만 깊은 생각을 해야하는 경우 이렇게 예제 몇 개 맞는 걸로 논리에 오류가 없을 것이라고 어림짐작하는 경우가 꽤 있다. 주의하자.

맞는 코드

#include <iostream>

using namespace std;

int arr[99999];

int main(void)
{
	int n=0, m=0;
	
	cin >> n >> m;
	
	int cnt = 0;
	int uniform = 0;
	
	int v1=0, v2=0;
	
	
	for(int i= 0 ; i< m; i++)
	{
		
		cin >> v1 >> v2;
		
		if(arr[v1]==0 && arr[v2]==0) //둘 다 0일 때는 집합 갯수+1 
		{
			cnt++;
			uniform++;
			arr[v1] = uniform;
			arr[v2]  = uniform;
		}
		
		else
		{
			if(arr[v1]!=0 && arr[v2]!=0) // 둘 다 0이 아니고
			{
				if(arr[v1] == arr[v2]) //둘이 같을 때는 pass
					continue;
				
				if(arr[v1] < arr[v2])
				{
					cnt -- ;
					int temp = arr[v2];
					int goal = arr[v1];
					for(int j = 1; j<= n; j++)
					{
						if(arr[j] == temp)
							arr[j] = goal;
					}
				}
				else if(arr[v1] > arr[v2])
				{
					cnt --;
					int temp = arr[v1];
					int goal = arr[v2];
					for(int j =1; j<=n; j++)
					{
						if(arr[j] == temp)
							arr[j] = goal;
					}
				}
			}
			else if(arr[v1] == 0 && arr[v2]!= 0)
			{
				arr[v1] = arr[v2];
			}
			else if(arr[v1]!=0 && arr[v2]==0)
			{
				arr[v2] = arr[v1];
			}
			else
				continue;
		}
		
	}
	for(int i= 1; i<=n; i++)
	{
		if(arr[i]==0)
			cnt++;
	}
	

	cout << cnt;

}

위의 코드와 거의 비슷하지만 집합 번호를 할당하는 변수와 집합 수를 세는 cnt 변수를 따로 두었고 집합 번호 할당 변수는 절대 감소하는 일 없게 해서 같은 집합이 아님에도 번호가 겹치는 일이 발생하는 것을 막았다.

다른 풀이

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

int n, m;
vector<int> adj[1002];
bool visited[1002];
void dfs(int now) {
	visited[now] = 1;
	for (int i = 0; i < adj[now].size(); i++){
		int next = adj[now][i];
		if (!visited[next]) dfs(next);
	}
}

int main() {

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	for (int j = 1; j <= n; j++) {
		sort(adj[j].begin(), adj[j].end());
	}
	
	int cnt = 0;
	for (int k = 1; k <= n; k++) {
		if (visited[k]) continue;
		dfs(k);
		cnt++;
	}
	cout << cnt;
}

다른 풀이는 DFS혹은 BFS를 활용하고 그래프를 2차원 배열(행렬)로 나타내어 반복문과 DFS로 배열을 순회하며 해결하는 방식이다. 이산수학에서 배운 그래프를 행렬로 나타내는 방식이 이럴 때 쓰이는구나 싶었다. 다양한 방식으로 생각해봐야겠다.