[leetcode] 685. Redundant Connection II

문제해석

리트코드 685번 문제.

rooted tree를 만들기위해 어떤 edge를 제거해야 하는가? (입력값은 항상 rooted tree에서 간선하나가 더 추가된 상태로 들어옴. 만약 제거할 수 있는 edge가 여러개 있다면 입력으로 늦게들어온 edge를 제거함)

* rooted tree ? : 루트노드를 제외한 모든 노드가 하나의 부모만을 가지는 트리

 

생각의 오류

처음엔 단순히 유향그래프의 사이클 발견즉시 해당 edge를 정답으로 찾는 알고리즘을 생각했다. 

하지만 해당 방법으로는 아래와 같이 사이클이 없는 그래프에서 정답을 찾지 못한다(실제로는 1->3 or 2->3 edge중 나중에 들어온 edge를 찾아야 한다)

따라서 이 문제는 문제의 조건을 이용하여 문제를 새롭게 정의해서 알고리즘을 만들어야 한다.

 

풀이

문제를 새롭게 정의한다는건 다음과 같다.

이 문제는 유향그래프이지만 완벽한 rooted tree에서 하나의 edge만 빠진 상태이다. 즉 정답이 되는 Edge는 부모노드가 2개를 가지는 노드와 연결된 edge들이나, 사이클을 이루고있는 인덱스 중 가장 늦게 들어온 edge들 중 하나가 된다.

따라서 유향그래프이지만, 부모노드가 2개라는 조건과 무향그래프를 검측하는 union find를 이용해서 풀 수 있다.

이를 정리하면 다음과 같다.

 

부모가 두개인 노드가 존재하는가?

존재하면 => 

      두번째나온노드 삭제하고 사이클 확인?

            => 사이클 있으면? => 첫번째 노드 삭제

            => 사이클 없으면? => 두번쨰 노드 삭제

존재안하면 => 사이클로 확인

 

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LC_685_Redundant_Connection2 {
    static class Solution {
        int size;
        int[] parentNode;

        public int find(int node) {
            if (parentNode[node]==node) {
                return node;
            } else {
                return find(parentNode[node]);
            }
        }

        public void union(int node1, int node2) {
            int node1Parent = find(node1);
            int node2Parent = find(node2);

            parentNode[node2Parent] = node1Parent;
        }

        public int[] findRedundantDirectedConnection(int[][] edges) {
            size = edges.length;

            // check if node got two parents node
            int[] firstParentNode = {-1,-1};
            int[] secondParentNode = {-1,-1};
            int[] edgeIndex = new int[size+1];
            Arrays.fill(edgeIndex,-1);

            for (int i=0; i<size; i++) {
                int u = edges[i][0];
                int v = edges[i][1];

                if (edgeIndex[v]==-1) {
                    edgeIndex[v]=i;
                } else {
                    // 부모2개인 노드가 있다면?
                    firstParentNode = edges[edgeIndex[v]];
                    secondParentNode = edges[i];
                }
            }

//            System.out.println("first"+Arrays.toString(firstParentNode));
//            System.out.println("second"+Arrays.toString(secondParentNode));

            parentNode = new int[size+1];
            for (int i=0; i<=size; i++) {
                parentNode[i]=i;
            }

            for (int[] edge: edges) {
//                System.out.println(Arrays.toString(edge));

                if (Arrays.equals(edge,secondParentNode)) {
                    continue;
                }

                int u = edge[0];
                int v = edge[1];


                // 싸이클이 존재
                if (find(u)==find(v)) {
                    if (Arrays.equals(firstParentNode,new int[]{-1,-1})) { // 부모가 두명이 아니면
                        return edge;
                    } else{ // 부모가 두명이면
                        return firstParentNode;
                    }


                } else {
                    union(u,v);
                }
            }

            return secondParentNode;
        }
    }

    public static void main(String[] args) {
        LC_685_Redundant_Connection2.Solution sol = new LC_685_Redundant_Connection2.Solution();
        System.out.println(Arrays.toString(sol.findRedundantDirectedConnection(new int[][]{{2,1},{3,1},{4,2},{1,4}})));
    }
}