[Java] 연결리스트 Union 알고리즘 구현하기
개요
아직 재학중인 후배의 과제라고 한다.
실력 발휘 좀 해 볼까~ 하고 코드를 짜 보았다.
과제
연결리스트를 이용하여 다음을 구현하시오.
- Make-Set(x) : 원소 x로만 이루어진 집합을 만든다.
- Find-Set(x) : 원소 x를 가지고 있는 집합을 알아낸다.
- Union(x, y) : 원소 x를 가진 집합과 원소 y를 가진 집합의 합집합을 만든다.
구현하기 전 문제 이해
구글에 서칭해보면 비슷한 내용을 많이 찾아볼 수 있다.
그런데 트리를 이용하여 구현한 코드들이 대부분이었다.
어쩔 수 없이 백지에서 써내려가야지...
아래는 문제를 이해하는데에 도움을 받은 정리이다.
Make-Set(x) { # 노드 x를 유일한 원소로 하는 집합을 만든다.
p[x] ← x;
}
Union(x, y) { # 노드 x가 속한 집합과 노드 y가 속한 집합을 합친다.
p[Find-Set(y)] ← Find-Set(x);
}
Find-Set(x) { # 노드 x가 속한 집합을 알아낸다. 노드 x가 속한 트리의 루트 노드를 리턴한다.
if (x = p[x]) then return x;
else return Find-Set(p[x]);
}출처 :
[알고리즘] 상호 배타적 집합의 처리
상호 배타적 집합의 처리 ※ 교집합은 다루지 않는다. • 지원할 연산 – Make-Set(x): 원소 x로만 이루어진 집합을 만든다 – Find-Set(x): 원소 x를 가지고 있는 집합을 알아낸다 – Union(x, y): 원소
yjg-lab.tistory.com
집합 처리에 대한 내용(이중연결리스트, 트리)부터 시간복잡도까지 잘 정리되어있으니
깊이 있는 공부를 원한다면 한 번 읽어 보는 것도 좋을듯하다.
코드 구현
Node.java
public class Node<T> {
public T data;
public Node<T> headNode;
public Node<T> nextNode;
public Node(T data) {
this.data = data;
this.headNode = this;
this.nextNode = null;
}
}: Node 클래스의 정의
제네릭을 이용하여 어떤 타입(T)이든 가능하게 만들었다.
새로운 Node를 하나 생성하면, headNode는 자기 자신을 가리키고 nextNode에는 null 값으로 설정된다.
Util.java
public class Util {
//////Make-Set(data)
public static <T> Node<T> makeSet(T data) {
return new Node<>(data);
}
//////Find-Set(node) : node가 속한 대장 head를 알아냅니다.
public static <T> Node<T> findSet(Node<T> node) {
return node.headNode; //그냥 모든 노드에는 대장 head에 대한 정보가 headNode에 담겨 있으므로 그것을 리턴합니다.
/*
if(node.headNode == node) { //만약 해당 노드의 headNode가 자기자신이라면, 본인이 대장 head라는 뜻이므로
return node; //자기 자신을 리턴합니다.
}
else return findSet(node.headNode);
*/
}
//////Union(X, Y) : node X가 속한 집합과, Y가 속한 집합을 합칩니다.
public static <T> void union(Node<T> n1, Node<T> n2) {
if(findSet(n1) != findSet(n2)) { //n1의 대장 head와 n2의 대장 head가 같지 않을 경우, 서로 다른 집합이라는 의미이므로 알고리즘을 수행합니다.
findTail(n1).nextNode = n2.headNode; //n1 집합의 꼬리를 찾아(null값) 그 위치에 n2의 headNode로 채워줍니다.
changeHead(n1.headNode, n2.headNode); //n2 집합의 모든 원소의 headNode를 n1의 headNode로 바꿉니다.
}
}
//node의 모든 headNode를 head로 바꿔주는 합수
public static <T> void changeHead(Node<T> head, Node<T> node) {
node.headNode = head;
if(node.nextNode != null) {
changeHead(head, node.nextNode);
}
}
//node의 꼬리 부분을 찾는 함수 (nextNode가 null인 노드를 찾을때까지 반복하는 재귀함수)
public static <T> Node<T> findTail(Node<T> node) {
if(node.nextNode == null) {
return node;
}
else return findTail(node.nextNode);
}
public static <T> void putNode(Node<T> node) {
System.out.println(node.data);
if(node.nextNode == null) {
System.out.println("이상 끝");
return;
}
else putNode(node.nextNode);
}
}: 과제의 핵심인 Make-Set, Find-Set, Union 함수와 부수적으로 만든 함수들을 정의
친절하게 주석을 달긴 했지만 편하게 이해할 수 있게끔
함수 하나씩 차근차근 설명해보도록 하겠다. (약간 막막하긴 한데)
makeSet(T data)
Node를 생성하는 함수이다.
사실 함수를 쓸 필요 없이 메인 함수에서 Node 클래스의 생성자로 바로 만들 수 있지만
과제에서 Make-Set을 구현하라 했으니 만들었다. (사용법은 아래 메인함수에서)
findSet(Node<T> node)
노드가 어떤 집합에 속해있는지 찾기 위한 함수이다.
해당 node가 속한 집합의 대장(headNode)이 리턴된다.
처음에는 위의 출처 자료를 보면서 코드를 짜느라 if문과 재귀함수로
headNode까지 거슬러올라가서 리턴하게끔 짰었는데, (주석 참고)
생각해보니 모든 노드의 headNode는 집합의 headNode를 가리키고 있지 않은가.
그래서 어이없게도 그냥 node.headNode를 리턴한다.
마찬가지로 함수를 쓸 필요 없이 "노드이름.headNode"을 이용하면
노드가 속한 집합의 대장노드를 찾을 수 있긴 하다.
union(node<T> n1, node<T> n2)
두 집합을 합치는 함수이다.
더 자세히 설명하자면, n1 노드의 집합에 n2 노드의 집합을 합치는 것이다.
n1 의 집합 꼬리에 n2 를 물게 하고, n2 집합 전체 노드의 headNode가 n1의 headNode를 가리키게 한다.
여기서 좀 더 예쁜 코드를 만들기 위해 findTail(), changeHead()라는 함수를 따로 만들어서 사용한 것이다.
이 두 함수의 설명은 아래에서 하겠다.
changeHead(Node<T> head, Node<T> node)
단순히 집합 내의 모든 노드의 headNode를 바꾸는 함수라고 설명하기에는 허점이 있다.
예를 들어, A라는 집합 내에는 N1, N2, N3, N4 네 개의 노드가 차례로 연결되어 있다고 가정하자.
두 번째로 연결된 N2를 changeHead(head, N2) 이와 같이 사용한다면
N2를 포함한 이후의 연결된 모든 노드들의 headNode는 head로 바뀌지만
N1에는 아무 일도 일어나지 않는다.
그러므로 이렇게 설명하는게 가장 정확하다.
주어진 node 포함 이후의 연결된 모든 노드들의 headNode를
주어진 head로 모조리 바꾸는 동작을 한다.
union() 함수에서 사용하기 위해 만들어졌기 때문에
당연히 헤드 노드만 넣는다는 가정이 있으니 이렇게만 짜도 정상적으로 동작한다.
만약 코드를 확장하여 '집합 내의 모든 노드의 headNode를 바꾸는 함수'를 만들어야 한다면
node.headNode부터 탐색하게끔 몇 줄이 더 추가되어야 한다.
findTail(Node<T> node)
주어진 node의 꼬리를 찾는 함수이다.
nextNode가 null값인 노드를 찾을 때 까지 재귀함수로 돌게끔 만들었다.
putNode(Node<T> node)
해당 노드부터 꼬리까지 연결된 모든 데이터를 출력하는 함수.
꼬리까지 모두 출력했다면 "이상 끝"을 출력.
처음부터의 전체 집합을 출력하고자 할 때는 putNode(findSet(node))와 같이 노드의 헤드를 넣어 주어야 한다.
main함수에서의 테스트를 위해 만들었다.
결과 테스트
사진과 같은 순서로 테스트를 진행함.
이해를 돕기 위해 직접 그림으로 그렸는데 꽤 잘 그린 것 같다.
Main.java
public class Main {
public static void main(String[] args) {
//노드 5개 생성
Node<String> n1 = Util.makeSet("a");
Node<String> n2 = Util.makeSet("b");
Node<String> n3 = Util.makeSet("c");
Node<String> n4 = Util.makeSet("d");
Node<String> n5 = Util.makeSet("e");
//노드 5개 출력
//Util.putNode(n1);
//Util.putNode(n2);
//Util.putNode(n3);
//Util.putNode(n4);
//Util.putNode(n5);
// (a, b) (c, d, e)
Util.union(n1, n2);
Util.union(n3, n4);
Util.union(n3, n5);
System.out.println(">>>>> n1이 속한 집합 출력 :");
Util.putNode(n1);
System.out.println(">>>>> n3이 속한 집합 출력 :");
Util.putNode(n3);
System.out.println(">>>>> n5이 속한 집합 출력 :");
Util.putNode(Util.findSet(n5));
// (a, b, c, d, e)
Util.union(n2, n4);
System.out.println(">>>>> n3이 속한 집합 출력 :");
Util.putNode(Util.findSet(n3));
}
}
결론
- 이중연결리스트에 대한 개념이 정리됨.
- 복잡하게 사용한 건 아니지만 제네릭이랑 좀 더 친해졌다.
- "A+" 받았다고 함.
- 추가적인 설명이 필요하다면 댓글을 남겨주시고, 코딩 과제 문의는 연락 바랍니다.