[백준/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로 배열을 순회하며 해결하는 방식이다. 이산수학에서 배운 그래프를 행렬로 나타내는 방식이 이럴 때 쓰이는구나 싶었다. 다양한 방식으로 생각해봐야겠다.