← 전체 회차
a-089-redundant-connection2026-08-16mediumleetcode #684neetcode150

중복된 연결

#depth-first-search#breadth-first-search#union-find#graph
↗ leetcode #684 · a-089-redundant-connection
01

문제

· problem
P.a-089-redundant-connection

중복된 연결

↗ leetcode #684

트리는 연결된 무방향 그래프이며 사이클이 없습니다. n개의 노드가 1부터 n까지 라벨을 가진 트리에서 시작하여 하나의 간선이 추가되었습니다. 추가된 간선은 1부터 n 사이의 서로 다른 두 정점을 선택했으며, 기존에 없던 간선입니다. 그래프는 edges 배열로 표현되며, edges[i] = [ai, bi]는 그래프의 노드 ai와 bi 사이에 간선이 있음을 나타냅니다. n개의 노드로 이루어진 트리가 되도록 제거할 수 있는 간선 하나를 반환하세요. 여러 답이 있다면, 입력에서 마지막에 나타나는 간선을 반환하세요.

제약
  • · n == edges.length
  • · 3 ≤ n ≤ 1000
  • · No repeated edges
  • · The graph is connected
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[[1,2],[1,3],[2,3]]
[2,3]
example 2input → output
[[1,2],[2,3],[3,4],[1,4],[1,5]]
[1,4]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    문제에서 "중복된"이란 무엇을 의미하나요?
  • ☐
    "입력에서 마지막"이라는 말은 정확히 무엇을 의미하나요?
  • ☐
    그래프는 방향 그래프인가요, 무방향 그래프인가요?
  • ☐
    왜 Union-Find가 이 문제에 적합한가요?
  • ☐
    경로 압축(Path Compression)은 어떤 역할을 하나요?
  • ☐
    여러 트리가 형성될 수 있나요?
  • ☐
    사이클을 형성하는 모든 간선을 반환해야 하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 부모 배열 초기화
○
par = [i for i in range(len(edges) + 1)]
○
par = [i for i in range(len(edges))]
○
par = list(range(len(edges)))
step 2· 계수(Rank) 배열 초기화
○
rank = [1] * (len(edges) + 1)
○
rank = [0] * (len(edges) + 1)
○
rank = list(range(len(edges) + 1))
step 3· Find 함수 (경로 압축 포함)│ 중첩
○
def find(n):
○
def find(n):
    if par[n] != n:
        par[n] = find(par[n])
    return par[n]
○
def find(n):
    while par[n] != n:
        n = par[n]
    return n
step 4· Union 함수 (Rank 기반 병합)│ 중첩
○
def union(n1, n2):
○
def union(n1, n2):
    p1, p2 = find(n1), find(n2)
    if p1 != p2:
        par[p1] = p2
    return p1 != p2
○
def union(n1, n2):
    par[n1] = n2
    return True
step 5· 사이클 감지 조건│ │ 중첩
○
if p1 == p2:
○
if n1 == n2:
○
if find(n1) != find(n2):
step 6· 모든 간선 순회 및 결과 반환
○
for n1, n2 in edges:
○
for i, (n1, n2) in enumerate(edges):
○
for n1, n2 in reversed(edges):
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
3
        par = [i for i in range(len(edges) + 1)]
4
        rank = [1] * (len(edges) + 1)
5
6
        def find(n):
7
            p = par[n]
8
            while p != par[p]:
9
                par[p] = par[par[p]]
10
                p = par[p]
11
            return p
12
13
        # return False if already unioned
14
        def union(n1, n2):
15
            p1, p2 = find(n1), find(n2)
16
17
            if p1 == p2:
18
                return False
19
            if rank[p1] > rank[p2]:
20
                par[p2] = p1
21
                rank[p1] += rank[p2]
22
            else:
23
                par[p1] = p2
24
                rank[p2] += rank[p1]
25
            return True
26
27
        for n1, n2 in edges:
28
            if not union(n1, n2):
29
                return [n1, n2]
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[[1,2],[1,3],[2,3]]
→
[2,3]
case 2
[[1,2],[2,3],[3,4],[1,4],[1,5]]
→
[1,4]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.