알고리즘) 프로그래머스 Graph, 사이클 제거

프로그래머스 고득점Kit - Graph

사이클 제거

프로그래머스

풀이

노드의 사이즈를 돌면서 하나씩 제거하고 사이클이 있는지 없는지 체크했다. 결과적으로 정확성 테스트는 다 맞지만, Cycle을 확인하는 메소드를 재귀로 호출하여 효율성은 다 틀린 것 같다. 이후 이 문제를 푼 분들의 로직을 보면서 가장 매력적인 로직을 찾아냈다.

전체 노드의 갯수 -1 개가 되면 사이클이 없다는 것이다. 다만, 컴포넌트의 갯수가 1개가 아닌 2개~n개일 때는 컴포넌트의 갯수도 같이 세줘야 한다는 것이다. 이 로직에 따라 코드를 짜봤지만, 효율적으로 짜지 못해서 그런지 똑같이 효율성이 0이 나왔다..

이 로직에 대해 궁금하신 분들은 여기에 들어가셔서 확인하시면 될 것 같습니다 :)

나중에 꼭 효율성까지 맞는 코드를 짜야겠다.

 

코드

import java.util.LinkedList;

public class KitGraphRemoveCycle {
    private static int solution(int n, int[][] edges) {
        LinkedList<Integer>[] nodes = inItNodes(n);
        nodes = connectNodes(edges, nodes);

        return getCnt(nodes, n);
    }

    private static int getCnt(LinkedList<Integer>[] nodes, int n) {   //
        int result =0;

        for(int i=1; i<=n; i++) {
//            System.out.println(i+"번 째");
            int[] visit = new int[nodes.length];
            result += i;
            for(int j=1; j<=n; j++) {
                if(i!=j && visit[j] !=1) {
                    if (isCycle(i, j, -1, visit, nodes)) {
                        result -= i;
                        break;
                    }
                }
            }
        }

        return result;
    }

    private static boolean isCycle(int expt, int current, int parent, int[] visit, LinkedList<Integer>[] nodes) {
        visit[current] =1;

        for(int next : nodes[current]) {
            if(next != expt) {
                if(visit[next] != 1) {
                    if(isCycle(expt, next, current, visit, nodes)) {
                        return true;
                    }
                } else if(next != parent){
//                    System.out.println("Except = " + expt + "\t curr = " + current + "\t next = "+ next+ "\t parent = " + parent);
                    return true;
                }
            }
        }

        return false;
    }


    private static LinkedList<Integer>[] inItNodes(int n) {
        LinkedList<Integer>[] result = new LinkedList[n+1];

        for(int i=1; i<=n; i++) {
            result[i] = new LinkedList<>();
        }
        return result;
    }

    private static LinkedList<Integer>[] connectNodes(int[][] edges, LinkedList<Integer>[] nodes) {
        for(int[] edge : edges) {
            nodes[edge[0]].offer(edge[1]);
            nodes[edge[1]].offer(edge[0]);
        }
        return nodes;
    }

    /*private static LinkedList<Integer> getCycles(LinkedList<Integer>[] nodes) {
        LinkedList<Integer> result = new LinkedList<>();
        for(int i=1; i<nodes.length; i++) {
            if(nodes[i].size() >2) {
                result.offer(i);
            }
        }
        return result;
    }*/

    public static void main(String[] args) {
        int n=8;
        int[][] edges = {{1,2},{2,3},{3,4},{4,5},{5,6},{6,7},{7,8},{8,1},{2,7},{3,6}};
//        int n=4;
//        int[][] edges = {{1,2},{1,3},{2,3},{2,4},{3,4}};
        System.out.println(solution(n,edges));
    }
}