1761. Minimum Degree of a Connected Trio in a Graph - Streak 7

연결된 "트리오"의 최소 차수를 구하는 문제이다.

 

트리오인걸 알려면, 두 정점은 거쳐봐야 안다.

 

이어진 두 정점 사이에 같이 알고 있는 정점은 트리오를 형성하므로, 그래프 탐색을 이용하면 찾을 수 있을 것 같다.

그 전에, 이전에 방문한 노드를 아는 방법이 필요하다.

 

dfs 로 순회한다고 할 때, 다음과 같이 지나친 정점을 표현해보자.

• pprev
• prev
• now
• next

pprev == next로 검사하면 된다.

 

pprev가 유일하지 않을 수 있는 문제가 있나?

위 그림의 경우, prev, now, next의 사이클이 잡히지 않을 수 있다.
확실한건 이전에 방문한 모든 pprev를 아는 것

 

그렇게 따지면, prev도 유일하지 않다.

 

그럴거면, 모든 정점에서 각각 2번 이동 후, 서로가 있는지 확인하는게 효율적이다.

시간복잡도는
O(n^3)

너무 습관대로 풀려 하지 말고, 현재 문제에 맞는 해답을 찾자.

class Solution {

    public int minTrioDegree(int n, int[][] edges) {

        List<Integer>[] g = new ArrayList[n+1];
        for(int i = 1; i<=n; i++) g[i] = new ArrayList<>();

        Set<Trio> trios = new HashSet<>();
        for(int i = 0; i < edges.length; i++){
            g[edges[i][0]].add(edges[i][1]);
            g[edges[i][1]].add(edges[i][0]);
        }

        for(int i = 1; i<=n; i++){
            dfs(trios, g, i, -1, i, 2);
        }

        if(trios.isEmpty()) return -1;

        int ret = Integer.MAX_VALUE;

        for(Trio trio: trios){
            int now = -6;
            now += g[trio.a()].size();
            now += g[trio.b()].size();
            now += g[trio.c()].size();
            ret = Math.min(ret, now);
        }
        return ret;
    }



    private void dfs(Set<Trio> trios, List<Integer>[] g, int start, int prev, int now, int remain){

        if(remain == 0){
            for(int next : g[now]){
                if(next == start){
                    trios.add(new Trio(start, prev, now));
                }
            }
            return;
        }
        for(int next : g[now]){
            if(next == prev) continue;
            dfs(trios, g, start, now, next, remain-1);
        }
    }
}



record Trio(int a, int b, int c){

    public Trio{
        if(a<b){
            int temp = a;
            a = b;
            b = temp;
        }

        if(b < c){
            int temp = b;
            b = c;
            c = temp;
        }

        if(a<b){
            int temp = a;
            a = b;
            b = temp;
        }
    }
}

6400만 연산 - 시간초과 아닐거같은데
시간초과가 났다.
![[image-1.png]]

다시 분석해보니, 간선의 개수때문에 O(E^3)가 발생할 수 있다.
차라리 정점 3개를 정해놓고 순회하는 것이 더 좋을 것 같다는 생각이 들었다.

이러면 진짜 O(n^3)의 시간복잡도가 된다.

class Solution {

    public int minTrioDegree(int n, int[][] edges) {
        Set<Integer>[] g = new HashSet[n+1];
        for(int i = 1; i<=n; i++) g[i] = new HashSet<>();
        for(int i = 0; i < edges.length; i++){
            g[edges[i][0]].add(edges[i][1]);
            g[edges[i][1]].add(edges[i][0]);
        }

        int ret = Integer.MAX_VALUE;
        for(int i = 1; i<=n; i++){
            for(int j = i+1; j<=n; j++){
                if(!g[i].contains(j)) continue;
                for(int k = j+1; k<=n; k++){
                    if(g[i].contains(k) && g[j].contains(k)){
                        ret = Math.min(g[i].size() + g[j].size() + g[k].size() - 6, ret);
                    }
                }
            }
        }

        return ret != Integer.MAX_VALUE ? ret : -1;
    }
}