Leetcode Java Redundant Connection

문제

Link

코드

class Solution {

  public int[] findRedundantConnection(int[][] edges) {
    int[] parents = new int[edges.length + 1];
    for (int[] edge : edges) {
      int a = this.find(parents, edge[0]);
      int b = this.find(parents, edge[1]);
      if (a == b) {
        return edge;
      } else {
        parents[a] = b;
      }
    }
    return new int[] {};
  }

  private int find(int[] parents, int index) {
    return parents[index] == 0 ? index : this.find(parents, parents[index]);
  }

}

결과

Link

설명

1. 트리 형태로 구성된 edges가 주어지면 n개의 노드로 구성된 트리가 되도록 제거할 배열을 찾는 문제이다.
   • edges[i] = [a_i, b_i] 는 그래프에서 노드 a_i와 b_i 사이에 edge가 있음을 나타낸다.
   • 제거할 edges 내 배열이 여러 개일 경우, 마지막 하나를 반환한다.

2. parents는 edges내 값들을 저장할 배열로, 최댓값으로 가능한 $edges.length + 1$ 크기의 정수 배열로 초기화한다.

3. edges의 모든 배열들을 순차적으로 각자 edge로 정의하여 아래를 반복한다.
   • a에 4번에서 정의한 find(int[] parents, int index) 메서드를 이용하여 parents 배열에서 edge[0] 값에 해당하는 부모 노드의 값을 넣어준다.
   • a에 4번에서 정의한 find(int[] parents, int index) 메서드를 이용하여 parents 배열에서 edge[1] 값에 해당하는 부모 노드의 값을 넣어준다.
   • a와 b가 동일한 경우 동일한 부모 노드를 가지고 있으므로 제거해야 할 edge이므로, edge를 주어진 문제의 결과로 반환한다.
   • a와 b가 동일하지 않은 경우, parents의 a번째 위치에 b를 넣어 부모 노드의 값을 저장하고 반복을 계속 수행한다.
4. 부모 노드의 값을 탐색하기 위한 find(int[] parents, int index) 메서드를 정의한다.
   • parents의 index번째 값이 0이면 부모가 존재하지 않으므로, index를 반환한다.
   • 위의 경우가 아니라면 index의 부모 노드 값으로 재귀 호출하여 더 상위 부모 노드의 값을 반환한다.

소스

Sample Code는 여기에서 확인 가능합니다.