코딩성장스토리

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 이 문제는 BFS,DFS 또는 유니온 파인드로 풀 수있다. 그래서 두 가지 풀이로 풀것이다 BFS와 유니온파인드이다. 유니온 파인드로 풀 수있는 이유는 바이러스 감염여부이고 이 그래프가 어떤 노드가 어떤 노드를 연결하고 있고는 중요하지 않고 같은 그래프인지 아닌지만 파악하면 되기 때문이다. 그래서 유니온 파인드로 풀어봤다. 그냥 간단하게 연결 된 쌍을 다 유니온 파인드 해버리면 결국 쌍이 이루어지는것들..

유니온 파인드 두 노드가 같은 그래프에 있는지 찾는 방법 그래프 알고리즘의 일종으로서 상호 배타적 집합, Disjoint-set Find -노드 x 가 어느 집합에 포함되어 있는지 찾는 연산 Union-노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산 parent[i]는 i의 부모가 무엇인지 나타내는 것, parent[i] =i 는 i가 루트 노드임을 나타냄(부모가 본인이므로) find함수 구현 int find(int x){ if (x==parent[x]){ return x; } else { return find[parent[x]]; } } 루트를 찾아 반환 하지만 이 함수의 문제점은 한쪽방향으로 치우칠 수 있다.(트리의 장점 소실) 이를 고치기 위해 오른쪽노드를 모두 루트노드에 연결하게 구..