[1스4코2파] # 227 LeetCode 684. Redundant Connection

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (227차)
[4코1파] 2023.01.13~ (219일차)
[1스4코1파] 2023.04.12~ (130일차)
[1스4코2파] 2023.05.03 ~ (108일차)

Today :

2023.08.19 [227일차]
graph
684. Redundant Connection

684. Redundant Connection

https://leetcode.com/problems/redundant-connection/

문제 설명

사이클이 없는 무방향 그래프가 주어질 때, 1에서 n까지 노드가 있는 트리로 시작된 그래프와 간선이 있다. 각 1부터 n까지 선택된 두 개의 서로 다른 노드를 가짐. 그래프는 길이 n의 배열 가장자리로 표시되며 여기서 edge[i] = [ai, bi]는 그래프에서 노드 ai와 bi 사이의 간선일 때,
n개의 노드로 이루어진 트리가 될 수 있도록 제거해야 하는 간선 구하기

문제 풀이 방법

union-find 서로소 집합 자료 구조 를 사용해서 find와 union method를 사용해서 중복되는 간선을 제거한다.
일단 주어진 각 n개의 parent node를 담는 리스트와 rank (깊이)를 담는 리스트가 필요하다.
find를 통해서 들어오는 n의 노드의 parnet를 찾고, union으로 n1, n2가 들어올 때 각 n1, n2 사이의 parnet와 rank를 비교해서 rank와 parent를 업데이트 한다.

내 코드

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        par = [i for i in range(len(edges)+1)]
        rank = [1] * (len(edges)+1)

        def find(n):
            p = par[n]
            while p!= par[p]:
                par[p] = par[par[p]]
                p = par[p]
            return p

        def getUnion(n1, n2):
            p1, p2 = find(n1), find(n2)

            if p1==p2:
                return False
            if par[p1] > par[p2]:
                par[p2] = p1
                rank[p1] += rank[p2]

            else:
                par[p1] = p2
                rank[p2] += rank[p1]

            return True

        for n1, n2 in edges:
            if not getUnion(n1,n2):
                return [n1,n2]  

증빙

여담

union find 알고리즘은 첨 봤는데 코드 대법관 덕분에 알게됨 굿