격자(grid)에서 분리 집합을 적용하기 위한 방법
분리집합 문제를 풀다가 격자에 적용할 상황을 맞딱뜨림.
고민해보다가 class 노드를 만들어서 관리하려 했지만 더 간단한 방법이 있을 것이라 판단하고 서칭함.
서칭을 해도 기본적인 이야기만 하길래 지피티랑 얘기 나눠보고, 그 방법을 정리함.
분리 집합?
- 1~N 까지의 노드가 존재
- 각 노드는 자기 자신만 있는 트리임
- union, find 연산으로 두 노드가 공통된 트리에 존재하는지 빠르게 확인할 수 있음.
- union : 두 노드를 합침
- find : 노드의 최고 조상 노드를 탐색
그럼 '노드가 가지고 있는 정보가 여러 개(i, j) 일 때는 어떻게 처리를 해주어야 할까?' 에서 출발함
결론부터 말하면 r, c 격자가 있을 때, 격자의 각 셀을 하나의 노드(집합)로 모델링함.
각 셀을 하나의 노드로 모델링 하는 방법은 (i*c + j) 인덱스로 표현하기.
그럼 r*c 길이의 1차원 parent 배열을 만들어서 관리가 가능함.
# 초기화: 각 셀을 자기 자신이 루트인 집합으로 설정
parent = [i for i in range(n * m)]
r, c = map(int, input().split())
for i in range(r):
for j in range(c):
idx = i*c + j
parent[idx] = idx
아래는 처음에 내가 접근했던 방법들
1. 다차원의 배열에서 관리하자.
보통 분리집합을 처음 적용하면 parent라는 1차원 배열을 만들어서 이곳에서 관리를 할 것임.
그럼 2차원으로 넘어가면 parents 같은 고차원 배열을 만든다? 더 복잡하게 들어가는 것 같음.
나같은 범부는 아이디어는 떠올려도 쉽게 고안 및 구현해내기는 힘들 것.
2. 배열을 여러 개 만들자
분리 집합은 size, rank, compress path 등 구현 방법이 여럿 있는데
size, rank 를 이용해 구현하면, size 혹은 rank 배열을 하나 더 만들어서 각 노드의 정보를 관리함.
물론 좋은 방법이겠지만
2차원 (x,y) 정보를 저장하려면 배열을 여러개로 만드는 것으로는 한계가 있다고 생각함.
3. 1차원 배열이되, 각 element를 node class의 객체로.
노드라는 것은 자료구조에서 처럼 class나 struct 등을 만들어서 구현해도 된다고 생각했음.
그리고 그 노드들의 정보를 업데이트 하면서 공통 조상을 찾음.
이 방법도 처음엔 괜찮아보였는데, 결국에는 분리집합이 아니라 그래프탐색 느낌이 진해지기 시작해서 발 뺌