[LeetCode] 684. Redundant Connection (파이썬/python)

🎈문제

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

 

🎁어떤 알고리즘?

1. union-find 알고리즘 (생각했던 코드가 동작하지 않아 검색 후 알게 된 알고리즘)

-> 각각의 idx를 노드라고 설정했을 때, 연결된 가장 작은 숫자의 노드를 idx의 값으로 가지는 방식으로 연결된 그래프를 찾는 방식이다.

 

 

💻코드

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:

            #  방문 표시와 부모 노드를 동시에 기록할 리스트
            par = [0] * (len(edges)+1)  

            def find(x):
                if par[x] == 0: # 처음 방문
                    return x
                return find(par[x]) # 부모 노드를 재귀로 찾아 올라감

            for x, y in edges:
                u = find(x)
                v = find(y)
                if u == v:  # 부모 노드가 같으면 순환하게 되므로 해당 노드 반환
                    return [x, y]
                par[v] = u  # 자기 자신보다 작은 값을 부모로 설정

🎄코드 설명

주석으로 대체

 

❌실패 사례

단순히 두 노드가 이미 접근한 적이 있으면 return 하게 했더니 

edges = [[3,4],[1,2],[2,4],[3,5],[2,5]] 인 경우, 답은 [2,5]인데 [2,4]가 출력되어 실패

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
            '''
            node_x와 node_y를 각각 비교하는데 둘 다 이미 visit에 있으면 return
            '''
            visit = [False for _ in range(1000)]
            for edge in edges:
                x,y = edge

                if visit[x]==True and visit[y]==True:
                    return edge
                visit[x] = True
                visit[y] = True