코딩테스트
[알고리즘] 2차원 배열에서의 Union Find 알고리즘의 적용
행복한 토마토
2024. 10. 1. 18:43
2차원에서의 유니온 파인드(Union-Find, 또는 Disjoint Set)는 일반적인 1차원 유니온 파인드의 아이디어를 확장한 것이다. 이를 2차원 배열에서 사용하려면 각 셀을 노드로 간주하고, 인접한 셀들(상하좌우)을 연결하는 방식으로 적용할 수 있다. 이 과정에서 최적화를 위해 그리디 알고리즘을 사용할 수 있는 방법도 있다.
1. 2차원 유니온 파인드 구조화
2차원 그리드에서 유니온 파인드를 사용하는 대표적인 문제로는 "섬의 개수 찾기", "2차원 퍼즐 해결" 등이 있다. 각 셀을 노드로 보고, 상하좌우로 인접한 셀들을 서로 연결할 수 있는 조건이 충족되면 Union 연산을 적용한다. Union-Find의 핵심은 셀들이 속한 그룹(집합)을 효율적으로 관리하는 것이다.
2차원 좌표의 변환
유니온 파인드의 기본은 1차원 배열로 관리하는 것이므로, 2차원 그리드를 1차원 배열로 변환하여 사용한다. 다음과 같이 2차원 배열에서의 좌표를 1차원 배열의 인덱스로 변환한다.
int index = x * columns + y;
Union 연산
인접한 셀들에 대해 값이 같거나 연결 가능한 조건이 충족되면 Union 연산을 통해 두 셀을 하나의 집합으로 병합한다.
Find 연산
Find 연산은 해당 셀이 속한 루트를 찾는 연산으로, 경로 압축(Path Compression)을 통해 성능을 최적화할 수 있다.
2. 그리디 알고리즘과의 결합
그리디하게 유니온 파인드를 사용하는 대표적인 예로는, 주어진 문제에서 가능한 가장 작은 비용이나 최대 이익을 빠르게 얻기 위해 그리디한 결정(선택)을 내리고, 그 선택에 따라 Union-Find를 업데이트하는 방식이 있다.
그리디 알고리즘 적용 예시
- 최소 스패닝 트리(MST): 그리디하게 가장 작은 간선을 선택하고, 그 간선을 통해 연결된 두 노드를 Union 연산으로 병합하여 최종적으로 최소 스패닝 트리를 구성한다. 크루스칼(Kruskal) 알고리즘이 이 방식의 대표적인 예이다.
- 동적 최적화 문제: 특정 상황에서 가장 작은 비용이나 시간에 따라 노드를 병합해 가는 문제들에서 그리디하게 결정된 순서에 따라 Union 연산을 수행한다.
3. 적용 예시: 백준, 섬의 개수
2차원 배열이 주어지고 각 셀이 물 또는 땅으로 이루어진 상황에서, 땅(1)인 셀들을 Union-Find를 사용하여 하나의 집합으로 병합하고, 최종적으로 섬의 개수를 구하는 방식이다.
- 모든 셀을 탐색하며, 땅(1)인 셀에 대해서 인접한 땅과 Union 연산을 수행한다.
- 최종적으로 각 셀의 루트를 확인하여 고유한 루트의 개수를 카운트하면 섬의 개수가 된다.
4. BFS와의 공통점 및 차이점
공통점
- 연결된 요소 탐색: 두 알고리즘 모두 연결된 요소(즉, 그래프나 그리드에서 서로 연결된 노드들)를 찾는 데 사용할 수 있다. 예를 들어, 2차원 그리드에서 연결된 섬을 찾을 때 둘 다 활용할 수 있다.
차이점
- 작동 방식
- BFS는 너비 우선으로 탐색다. 시작 지점에서 가까운 노드(셀)부터 차례대로 큐(queue)를 사용해서 주변 노드를 모두 탐색한다. BFS는 탐색 알고리즘으로, 노드들이 어떻게 연결되어 있는지 알아내기 위해 각 노드를 직접 방문한다.
- 유니온 파인드는 "두 노드가 같은 그룹에 속하는지" 또는 "두 그룹을 하나로 합칠 수 있는지"를 효율적으로 처리하는 집합 관리 알고리즘이다. 노드를 직접 방문하기보다는 노드들 간의 연결 관계만을 관리한다. 노드가 속한 그룹을 트리 형태로 관리하고, 이 트리에서 그룹의 대표 노드를 찾거나 그룹끼리 합칠 때 쓰인다.
- 자료 구조
- BFS는 큐(queue)를 사용해서 현재 노드에서 연결된 이웃 노드를 순차적으로 처리하고 모든 노드를 방문하면서 탐색을 완료한다.
- 유니온 파인드는 트리와 배열을 사용해 각 노드가 속한 그룹의 정보를 저장한다. parent[] 배열이 노드의 부모를 저장하고, rank[] 배열이 트리의 깊이를 관리한다.
- 시간 복잡도
- BFS는 그래프에서 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(N) (N은 노드의 개수)이다.
- 유니온 파인드는 find()와 union() 연산을 매우 효율적으로 처리할 수 있어요. 경로 압축과 트리 높이 조절을 사용하면 각 연산의 시간 복잡도는 거의 상수 시간으로 처리할 수 있어서 O(α(N))이 된다. 여기서 α는 매우 느리게 증가하는 아커만 함수의 역함수이다.
- 사용 목적
- BFS는 노드들을 방문하면서 탐색하고, 연결된 구성 요소들을 확인하거나 탐색 순서에 따른 문제를 해결하는 데 적합하다. 예를 들어, 최단 경로 탐색이나 미로 찾기 등에 자주 쓰인다.
- 유니온 파인드는 노드들 간의 연결 관계를 효율적으로 관리하고, 서로 다른 집합을 병합하거나 같은 집합에 속하는지 여부를 빠르게 확인하는 데 사용된다. 예를 들어, 서로소 집합 문제나 최소 스패닝 트리(Kruskal 알고리즘) 등에서 유용하다.
5. 예시로 보는 차이점 : 백준, 섬의 개수
BFS 예시
BFS는 시작 지점에서 주변 노드를 하나씩 방문하면서, 같은 그룹의 모든 노드를 찾아낸다. 예를 들어, 섬을 찾는 문제에서 BFS는 다음과 같이 동작한다.
- 땅(1)을 만나면 그 지점부터 BFS를 시작.
- 인접한 땅들을 큐에 넣고, 큐에서 하나씩 꺼내면서 다시 그 주변의 땅들을 찾음.
- 더 이상 방문할 수 있는 땅이 없으면 섬 하나를 찾았다고 간주.
유니온 파인드 예시
유니온 파인드는 각 땅이 서로 연결될 때마다 같은 그룹으로 합친다. 섬을 찾는 문제에서 유니온 파인드는 다음과 같이 동작한다:
- 땅(1)을 만나면 해당 지점을 새로운 그룹으로 만듦.
- 인접한 땅이 있으면 두 땅을 합쳐서 같은 그룹으로 만듦(Union).
- 마지막에 각 그룹의 대표 노드를 통해 몇 개의 섬(그룹)이 있는지 셈.
요약
- BFS는 탐색 알고리즘으로, 시작 노드에서 가까운 노드들을 순차적으로 방문하면서 연결된 요소를 찾는다.
- 유니온 파인드는 집합 관리 알고리즘으로, 노드들 간의 연결 상태를 효율적으로 관리하고, 같은 그룹인지 또는 다른 그룹을 합칠지 판단한다.
결론적으로 BFS는 직접적인 탐색에 더 적합하고, 유니온 파인드는 연결된 그룹을 빠르게 관리하고 병합하는 데 효율적이다.
import java.util.Scanner;
public class 섬의개수 {
static int w, h;
static int[][] map;
static int[] parent;
static int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1};
static int[] dy = {0, 0, -1, 1, -1, 1, -1, 1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
w = sc.nextInt();
h = sc.nextInt();
if (w == 0 && h == 0) break;
map = new int[h][w];
parent = new int[h * w];
// 지도 입력 받기
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
map[i][j] = sc.nextInt();
int idx = i * w + j;
parent[idx] = idx; // 초기에는 각 칸이 자기 자신이 루트
}
}
// 유니온 파인드로 각 섬을 연결
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (map[i][j] == 1) { // 땅일 때만 연결 시도
for (int d = 0; d < 8; d++) {
int ni = i + dx[d];
int nj = j + dy[d];
if (isInBounds(ni, nj) && map[ni][nj] == 1) {
union(i * w + j, ni * w + nj);
}
}
}
}
}
// 섬의 개수 세기
int count = 0;
boolean[] counted = new boolean[h * w];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (map[i][j] == 1) {
int root = find(i * w + j);
if (!counted[root]) { // 아직 센 적 없는 루트면 새로운 섬
count++;
counted[root] = true;
}
}
}
}
System.out.println(count);
}
}
// 유니온 파인드: 루트 찾기
static int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]); // 경로 압축
}
// 유니온 파인드: 두 노드 연결
static void union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA != rootB) {
parent[rootA] = rootB;
}
}
// 범위 확인
static boolean isInBounds(int x, int y) {
return x >= 0 && x < h && y >= 0 && y < w;
}
}