2024.03.09 - 도넛과 막대 그래프

[wlsgh7608]

문제 - 링크

문제 풀이

• 도넛, 막대, 8자 그래프들의 개수와 시작 지점 구하기

시작 지점 판별

• 시작 지점은 무작위로 하나 주워지고 다른 그래프들을 가리키고 있음
• 따라서 시작 지점으로 들어오는 간선은 0개, 시작 지점에서 나가는 간선은 2개 이상임

int start = -1;

for(int i = 0; i<N;i++){
    if(in[i] == 0 && out[i]>=2){
        start = i;
    }
}

그래프 모양 판별

• 도넛 모양
  

• 막대 모양
  

• 8자 모양
  

• dfs을 이용하여 그래프를 탐색한다.

• 만약, 해당 정점에서 나가는 간선의 개수가 2개 이상이면 해당 정점이 있는 그래프는 8자 그래프이다.

• 또한, 시작 지점으로 돌아 오는 경우 이 그래프는 도넛 모양 그래프이다.

    void dfs(int v,int start){
        if(adjList[v].size()>=2){
            isEight = true;
            return;
        }

        for(int next : adjList[v]){
            // 그래프 탐색시 시작 지점으로 돌아 온다면 도넛모양
            if(next == start){
                isDoughnut = true;
                return;
            }
            dfs(next,start);
        }

    }

코드

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

class Solution {
    int[] in;
    int[] out;
    List<Integer>[] adjList;

    boolean isEight;
    boolean isDoughnut;

    static final int DOUGHNUT_IDX = 1;
    static final int STICK_IDX = 2;

    static final int EIGHT_IDX = 3;


    void init(int[][] edges){

        int N = -1;
        for(int[] edge : edges){
            N = Math.max(N,edge[0]);
            N = Math.max(N,edge[1]);
        }
        in = new int[N+1];
        out = new int[N+1];
        adjList = new ArrayList[N+1];
        for(int i = 0; i<=N;i++){
            adjList[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            int start = edge[0];
            int end = edge[1];
            // start -> end
            in[end]++;
            out[start]++;

            adjList[start].add(end);
        }

    }


    void dfs(int v,int start){
        if(adjList[v].size()>=2){
            isEight = true;
            return;
        }

        for(int next : adjList[v]){
            // 그래프 탐색시 시작 지점으로 돌아 온다면 도넛모양
            if(next == start){
                isDoughnut = true;
                return;
            }
            dfs(next,start);
        }

    }



    public int[] solution(int[][] edges) {
        int N = -1;
        for(int[] edge : edges){
            N = Math.max(N,edge[0]);
            N = Math.max(N,edge[1]);
        }

        init(edges);


        int start = -1;

        for(int i = 0; i<N;i++){
            if(in[i] == 0 && out[i]>=2){
                start = i;
            }
        }


        int[] answer = new int[4];

        answer[0] = start;

        for(int next: adjList[start]){
            // 그래프 탐색
            dfs(next,next);
            if(isEight){
                answer[EIGHT_IDX] += 1;
            }else if(isDoughnut){
                answer[DOUGHNUT_IDX] += 1;
            }else{
                answer[STICK_IDX] += 1;
            }
        }


        return answer;
    }

}

시간, 공간 복잡도

• 시간 복잡도 : O(E)
• 공간 복잡도 : O(E)

실행 시간