[프로그래머스] 카카오 2024 도넛과 막대 그래프

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/258711

프로그래머스

 

2. 접근방법

먼저 생성된 정점을 찾아야 한다.

그림을 보면 생성된 정점 (4) 만 들어오는 간선이 없는 것을 볼 수 있다.

 

하지만 이 그림에서는 2번과 4번 정점이 들어오는 간선이 없는데,

2번이 생성된 정점, 4번은 막대 그래프의 시작 정점이다.

 

이 두가지 케이스는

 

제한사항에 적혀 있는

도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다. 를 이용하여 구분가능.

정점에서 나가는 간선이 막대 그래프는 1개 뿐이고, 생성된 정점은 2개 이상이어야 한다.

 

정리하면

***들어오는 간선이 없고 나가는 간선이 2개 이상이면 시작정점

 

이제 생성된 정점에서 출발하는 간선이 각각의 그래프에 하나씩 연결 되므로,

각 간선을 탐색하여 그래프의 특징을 찾으면 된다.

 

먼저 도넛 그래프의 경우

순환 (탐색 하다 같은 정점에 다시 도달) 하면 도넛 그래프

 

막대 그래프의 경우

탐색하다 끝에 도달하면 나가는 간선이 없어짐.

나가는 간선이 없는 정점이 있을 경우 막대 그래프.

 

8자 그래프의 경우

유일하게 나가는 간선이 2개인 정점이 있음

탐색하다 나가는 간선이 2개인 정점이 있을 경우 8자 그래프.

 

위 3가지 조건을 이용하여 그래프의 갯수를 세어서 반환 하면 된다.

3. 자바 코드

// 도착하는게 없고 출발이 2개 이상이면 시작정점

// 시작부터 찾고
// 시작에서 뻗어나가는 얘들의 특징 찾기

// 탐색해서 출발 2개인 정점 있으면 8자
// 탐색해서 기존 꺼로 돌아오면 도넛
// 탐색해서 끝이 있으면 막대

import java.util.ArrayList;

class Solution {
    ArrayList<Integer>[] edgeLists;


    public int[] solution(int[][] edges) {

        // 생성점 찾기
        int startNum = findStart(edges);


        if (startNum == 0) {
            return new int[]{-1};
        }
        int[] answer = new int[4];
        answer[0] = startNum;
        for (int startEdge : edgeLists[startNum]) {
            int form = dfs(startEdge,startEdge);
            answer[form]++;
        }
        return answer;
    }

    public int dfs(int n, int startEdge) {
        ArrayList<Integer> arr = edgeLists[n];
        if(arr.size() == 0){
            return 2;
        }
        if(arr.size() == 2){
            return 3;
        }
        if(arr.get(0) == startEdge){
            return 1;
        }
        return dfs(arr.get(0),startEdge);
    }

    public int findStart(int[][] edges) {
        int max = 0;
        for (int[] edge : edges) {
            max = Math.max(max, Math.max(edge[0], edge[1]));
        }
        edgeLists = new ArrayList[max + 1];
        for (int i = 0; i < max + 1; i++) {
            edgeLists[i] = new ArrayList<>();
        }
        int start[] = new int[max + 1];
        int end[] = new int[max + 1];
        for (int[] edge : edges) {
            start[edge[0]]++;
            end[edge[1]]++;
            edgeLists[edge[0]].add(edge[1]);
        }
        for (int i = 1; i < max + 1; i++) {
            if (end[i] == 0 && start[i] > 1) {
                return i;
            }
        }
        return 0;
    }
}

4. 마치며

이해하면 어렵지 않은데,

처음 문제를 맞닿았을 때 뭔가 위압감이 느껴졌다.