[그래프] 유니온 파인드

 

 

 

 

 

유니온 파인드

여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산과

두 노드가 같은 집합에 속해 있는지를 확인하는 find연산으로 구성되어 있는 알고리즘

(엄밀히 말하면 그래프 영역이라고 보기에 약간 무리가 있으나 실제로 그래프 문제에서 부분 알고리즘으로 많이 사용됨)

 

find연산이란?

자신의 대표 노드를 찾아주는 연산

 

핵심이론

union, find 연산을 완벽히 이해하는 것

• UNION : 각 노드가 속한 집합을 1개로 합치는 연산
  → 노드 a, b가 a ∈ A, b ∈ B일 때 UNION(a,b) 는 A ∪ B를 말함
• FIND : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산
  → 노드 a가 a ∈ A일 때 find(a)는 A집합의 대표노드를 반환
  (대표노드를 선택하는 기준은 두 값중 큰/작은 수와 같이 어느 하나의 기준만 정해지면 된다.)

 

원리 이해

Step 1) 대표노드 배열 초기화

알고리즘 실행 전 초기화를 진행 - 대표노드를 저장하는 배열 사용
1차원 배열을 이용하여 배열에 각 노드의 대표 노드를 저장한다.

처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표노드가 된다
(각 노드가 대표 노드이므로 배열은 자신의 인덱스로 초기화)

1	2	3	4	5	6
1	2	3	4	5	6

 

Step 2) UNION연산

 

임의의 2개의 노드를 선택해 각각의 대표노드를 찾아 연결하는 UNION연산 수행

위의 과정은 지문으로 특정 노드를 엣지(간선)으로 연결한 그래프로써 제시하거나

지문으로 어떤 어떤 값끼리 연결되었다고 가정하고, 그 가정에서 특정 노드가 연결되어있는지 여부를 물어보는 형태.

1, 4와 5, 6을 UNION연산으로 연결 → 배열[4]는 `1`로 배열[6]은 `5`로 업데이트 (대표노드로 업데이트)

 

(초기 상태에서 UNION연산시 find를 안한 이유는 실질적으로 find를 했지만 대표노드가 현재노드 그 자체의 값이였기 때문에 실질적으로 find는 했지만 그 과정을 생략 - 로직이라면 초기 상태인지에 대한 조건문으로 건너뛰지않을까요?
결론은 find는 무조건 한다. but 초기 상태에서는 불필요한 연산이 되므로 find연산을 생략하든 안하든 상관없음 )

 

ex) UNION(1, 4) ①─④ /  UNION(5, 6) ⑤─⑥ (하나의 집합으로 만든다는 의미는 그래프에서는 연결을 뜻함)

 

대표노드가 되는 기준을 작은값으로 가정할때 4의 대표노드는 1, 6의 대표노드는 5로 업데이트
(1과 5는 이미 대표노드가 5이므로!)

1	2	3	4	5	6
1	2	3	1	5	5

 

∴ 4는 1로 연결되었고 1을 대표노드로 갖는다, 6은 5로 연결되었고 5를 대표노드로 갖는다.

 

UNION연산은 첫 연산 이후 모든 연산은 대표노드 끼리 연결한다. 

첫 UNION연산시 하나도 연결이 되어있지 않으므로 (그 자체로 대표노드이기 때문)

 

위 과정은 그래프상의 연결을 UNION연산의 예시를 들어 배열에 반영하기 위해 진행한 과정이다.

Step 3)로 넘어가 실제 UNION(4, 6) 연산을 수행해본다.

 

Step 3) FIND연산

FIND연산은 자신이 속한 집합의 대표 노드를 찾는 연산으로, 단순히 대표노드만 찾는 역할이 아닌 그래프를 정돈하고 시간복잡도를 향상시킨다.

예를들어 그래프에서 Step 02연산을 진행하여 임의의 노드를 엣지로 연결하고,

특정 엣지로 연결되어있는 그래프상에서 특정 두 노드값이 서로 연결되어있는지 여부를 판단하는 연산이 바로 FIND연산이다.

FIND연산을 진행하여 대표노드를 찾은뒤 대표노드끼리 연결한다.

1)  대상 노드 배열에 index값과 value값이 동일한지 확인
2)  동일하면 대표노드, 동일하지 않으면 현재 value가 가리키는 index로 이동
3)  index == value 즉, 대표노드를 찾을 때 까지 1) ~ 2) 작업 반복 (재귀함수 구현)
4)  대표노드로 도달하면 재귀함수를 빠져나오면서 거치는 모든 노드 값을 루트노드 값으로 변경함
      (루트노드 = 대표노드의 value)

 

UNION(4, 6) → ④의 대표노드 탐색 = find(4)

• find(4) : ①
  1. 4의 index와 value가 일치하는지 확인
  2. 같으면 대표노드, 다르면 value값을 index로 갖는 곳으로 이동
     (4의 대표노드는 1 → 일치하지 않으므로 1 위치로 이동)
  3. 이동한 index와 대상 value가 일치하는지 확인
  4. 같으면 대표노드 다르면 value값을 index로 갖는 곳으로 이동
     (1의 대표노드는 1로 일치하므로 대표노드는 1)
  5. index == value 즉, 대표노드를 찾을 때 까지 1 ~ 2 작업을 반복한다.

1	2	3	4	5	6
1	2	3	1	5	5

• find(6) : ⑤
  1. 6의 index와 value가 일치하는지 확인
  2. 같으면 대표노드, 다르면 value값을 index로 갖는 곳으로 이동
     (6의 대표노드는 5 → 일치하지 않으므로 5위치로 이동)
  3. 이동한 index와 대상 value가 일치하는지 확인
  4. 같으면 대표노드 다르면 value값을 index로 갖는 곳으로 이동
     (5의 대표노드는 5로 일치하므로 대표노드는 5)
  5. index == value 즉, 대표노드를 찾을 때 까지 1 ~ 2 작업을 반복한다.

1	2	3	4	5	6
1	2	3	1	5	5

 

∴ 노드①과 노드⑤ 가 연결되었지만 실제로는 노드④와 노드⑥이 연결된것과 같다. (④-①-⑤-⑥으로 빙 둘러서 연결됨)

→ UNION(4,6)을 했지만 실제로는 노드①과 노드⑤ 가 연결되었고 이는 노드④와 노드⑥이 연결하는것과 동일한 결과

따라서 UNION(4,6) 과 대표노드간의 UNION연산인 UNION(1, 5)를 함께 진행해준다.

1	2	3	4	5	6
1	2	3	1	5 1	5 1

 

대표노드 도달 후 거친 모든 노드값을 루트노드 값으로 변경함.

이를 통해 최종 루트노드는 1이된다. (1, 5 중에서)

따라서 최종 루트 노드가 동일하게 1이 되었으므로... 두 노드는 같은 집합 안에 존재한다고 여부를 판단할 수있게 된다.

경로압축

실제 그래프에서 여러 노드를 거쳐야 하는 경로에서 그래프를 변형해 더 짧은 경로를 갈 수 있도록 함으로써 시간복잡도를 효과적으로 줄이는 방법.

 

즉, 특정 두 노드가 하나의 집합에 속하는지, 연결되어 있는지 아닌지만 보면 된다.

어떤 경로로 연결되었는지 알 필요는 없다.

두 노드가 연결되어 있다. 아니다, 한 집합이다 아니다 여부만 알면 된다.

그렇기에 그래프로 변경해도 전혀 문제가 발생하지 않는다.

 

극단적인 예로 

①-②-③-④-⑤-⑥ 과 같이 `연결`되어 있고 이를 배열로 표현하면 아래와 같다.

1	2	3	4	5	6
1	1	2	3	4	5

연결 되어 있기 때문에 두 노드를 기준으로 더 작은값을 기준으로 대표노드를 저장한다.

이때 find(6)연산을 하게되면 

⑥ → ⑤ find(6) 5 번 인덱스로 이동

⑤ → ④ find(5) 4 번 인덱스로 이동

④ → ③ find(4) 3 번 인덱스로 이동

③ → ② find(3) 2 번 인덱스로 이동

② → ① find(2) 1  번 인덱스로 이동

① → ① find(1) (일치하므로 6의 대표노드 1로 변경)

위의 순서처럼 재귀로 find 함수를 호출하게 된다.

재귀함수형태로 호출되면서 지나온 모든 경로를 1로 변경한다.

1	2	3	4	5	6
1	1	1	1	1	1

 

이상태에서 다시한번 find(6)을 하게되면 한번에 1을 찾아가게 되므로 시간복잡도가 처음 UNION연산을 했을 때 보다 확연히 줄어들게된다.

 

 

union 함수의 목적은 두 부모 노드를 동일하게 만들어 하나의 그룹임을 확인할 수 있는 상태로 만드는 것