[구름톤 챌린지] 4주차 학습 일기 #1 (16일차)

문제 링크

구름LEVEL

문제 설명

 

입력 

출력

N개의 섬 사이에 존재하는 연합의 수를 출력한다.

 

 

문제 이해

양방향을 확인하는 것까지는 쉽게 구현을 했고 이후 BFS를 이용하여 문제를 해결한 뒤 인터넷의 다른 사람들의 해결 코드를 살펴보다가 Union - Set 알고리즘을 이용한 코드가 흥미로워 코드를 변경하였다.

1. 초기 입력은 단방향이다.

2. 양방향인지 검사해준 후 (3) BFS를 사용하거나, (4) parent 배열(연합 정보)을 만들어 연합의 root를 저장한다.

3.BFS

3-1. 양방향인걸 이미 검증했으니, 그래프 간 연결을 확인해보면 된다.

3-2. 그래프의 연결 확인이 모두 끝나면 방문했던 섬들을 다 방문했다고 표시해 준 뒤, 연합의 개수를 1 올려준다.

4.Union-Set

4-1. N 크기만큼 parent 배열을 만들어주고, 자기 자신의 번호를 저장한다.

4-2. find함수와 union함수를 제작해 같은 연합은 모두 같은 번호로 만들어준다.

4-3. parent에 존재하는 숫자 종류의 개수가 연합의 개수이다.

 

 

문제 해결

 

1. find 함수와 union함수를 제작한다.

int find(int x){
    if(x == parent[x]){
	  return x;
	}
    else{
	  int temp = x;
	  while(temp != parent[temp]){
		  temp = parent[temp];
	  }
	  return temp;
	}
}
void island_union(int x, int y){
    int tx = find(x);
    int ty = find(y);
    if (tx > ty)
        parent[tx] = ty;
    else
        parent[ty] = tx;
}

 

2. 양방향인걸 확인하면 union 함수를 실행한다.

for(int i = 1; i <= n; i++){
        for(int j : island[i]){
            if(find(island[j].begin(), island[j].end(), i) != island[j].end())
                island_union(i,j);
        }
}

 

3.  연합의 개수를 만들어줄 set 자료구조를 이용한다.

set<int> u;
for(int i = 1; i <= n; i++){
  u.insert(find(i));
}

 

 

문제 후기

개인적으로는 이번 문제가 챌린지를 하면서 제일 어려웠던 것 같다. 처음써보는 Union-Set알고리즘을 쓴 게 이유인 것 같은데, Union-Set 알고리즘은 추후에 따로 정리하여 따로 포스팅할 예정이다. 추가로 아쉬웠던 점은 마지막 set에 데이터를 넣는 과정에서 find(i)를 쓰는 것과 parent[i]를 쓰는 것이 무슨 차이가 있는지를 해결하지 못했다. 차이점을 알게 되면 따로 수정해서 작성할 예정이다.

 

 

 

전체 코드

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

vector<vector<int>> island(2001);
int parent[2001];
set<int> u;
int n,m;

void init(){
    for(int i = 1; i <= n; i++)
        parent[i] = i;
}

int find(int x){
    if(x == parent[x]){
	  return x;
	}
    else{
	  int temp = x;
	  while(temp != parent[temp]){
		  temp = parent[temp];
	  }
	  return temp;
	}
}

void island_union(int x, int y){
    int tx = find(x);
    int ty = find(y);
    if (tx > ty)
        parent[tx] = ty;
    else
        parent[ty] = tx;
}

int main(){
    cin >> n >> m;
    int f,s;
    for(int i = 0; i < m; i++){
        cin >> f >> s;
        island[f].push_back(s);
    }
    init();
    int count = 0;
    for(int i = 1; i <= n; i++){
        for(int j : island[i]){
            if(find(island[j].begin(), island[j].end(), i) != island[j].end())
                island_union(i,j);
        }
    }
    for(int i = 1; i <= n; i++){
			u.insert(find(i));
			cout << parent[i] << " " << find(i) << endl;
		}
    cout << u.size();
}