안녕하세요 이번 시간에는 유니온 파인드 문제에 대해 분석해보는 시간을 갖도록 하겠습니다.
유니온 파인드란 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘입니다. 각 노드가 연결되어 있는 집합 중 가장 작은 노드를 대표 노드로 정의한 후 union 연산과 find 연산을 수행합니다. 이 때 대표 노드는 자기 자신의 값으로 초기화가 되어야 합니다.
find 연산의 경우 현재 노드와 대표 노드가 같다면 현재 노드를 리턴하고, 다르다면 현재 노드의 대표 노드를 재귀 함수로 find 연산한 결과를 리턴합니다. (return parent[a] = find(parent[a])
union 연산의 경우 비교할 노드 2개를 find 연산하여 얻은 각각의 대표 노드끼리 다르다면 하나의 노드의 대표 노드를 다른 하나의 대표 노드로 변경합니다. (parent[b] = a)
유니온 파인드는 요소들의 연결 관계를 고려하여 하나의 묶음으로 처리해야 하는 경우의 문제에서 적용됩니다. 주로 연결 여부를 판별하는데 사용되며 불필요한 탐색을 줄일 수 있기 때문에 시간 초과 문제를 해결할 수 있습니다.
백준 1717(집합의 표현) 문제의 경우 0은 두 원소를 합치는 연산, 1은 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 진행할 때의 결과를 출력하는 문제입니다. 위에서 언급한 유니온 파인드 로직을 구현하면 쉽게 풀 수 있습니다.
백준 1976(여행가자) 문제의 경우 여행 경로의 가능 여부를 출력하는 문제입니다. 두 경로가 이어져 있으면 union 연산을 실행하고, 경로의 도시를 find 연산으로 대표 노드가 모두 같으면 이어져 있는 경로라는 것을 알 수 있습니다. 여기서 주의할 점은 find 연산 로직이 1부터 N까지 범위에서 적용되기 때문에 1부터 범위를 설정해야 합니다. 추가적인 팁으로 int로 0,1을 boolean으로 파싱하면 false로 인식하기 때문에 int 값으로 파싱한 후 각각 0과 1인지를 비교해야 합니다.
백준 1043(거짓말) 문제의 경우 거짓말쟁이로 알려지지 않으면서 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 문제입니다. 문제를 다르게 해석해보면 참가하는 파티에 진신을 아는 사람이 없는 파티의 수를 구하는 문제이기 때문에 각 파티 별로 union 작업을 진행하여 진실을 알고 있는 사람 배열을 탐색해 병합한 파티의 첫 사람의 대표 노드와 같다면 진실을 아는 사람이 존재하지 때문에 NO를 출력합니다. 여기서 유니온 파인드로 병합했기 때문에 하나의 원소만 체크해도 다른 원소들과 연결되어 있어 모든 파티원을 체크할 필요가 없게 됩니다.
