[프로그래머스] 2024 KAKAO WINTER INTERNSHIP - 도넛과 막대 그래프 (Java)

 

프로그래머스

 

풀이

문제를 보고 유니온-파인드로 그룹을 찾아야하나 싶었다. 하지만 문제에서 조건으로 주어진 임의로 생성된 정점 때문에 해당 방식으로 접근하기가 쉽지 않았다.

 

모든 경로를 탐색해서 그래프의 형태를 파악하지 않아도 해결할 수 있는 방법이 있었다.

각 그래프에서 특징이 되는 노드 하나만 찾아내는 방식이다.

 

각 그래프들을 식별할 수 있는 노드의 특징은 다음과 같다.

 

- 임의로 생성된 정점 : 모든 그래프를 연결하는 정점이기 때문에 들어오는 간선이 없고 나가는 간선만 존재한다. 문제에서 그래프 갯수는 2개 이상이라 했으므로 간선은 2개 이상이다. 

- 막대 그래프 : 막대 그래프의 마지막 노드를 주목하자. 나가는 간선은 없고 1개 이상의 들어오는 간선만 있다.

- 8자 그래프 : 두 개의 도넛 그래프 공유하는 노드(8자의 중심)를 주목하자. 나가는 간선, 들어오는 간선이 2개 이상이다.

- 도넛 그래프 : 앞서 구분된 그래프들을 활용할 수 있다. (임의로 생성된 정점에 연결된 그래프 갯수==정점에서 나가는 간선 수) - (막대 그래프 갯수) - (8자 그래프 갯수)

 

여기서 개인적으로 헷갈렸던 부분이 있다면 왜 간선 갯수를 n개가 아닌 "n개 이상"이라고 봐야하는지였다.

이는 임의로 생성된 정점 때문인데, 각 그래프만 생각한다면 정확한 간선 갯수가 정해져 있겠지만 임의로 생성되는 정점이 연결될 수도 있기 때문에 n개 이상으로 바라봐야한다.

 

이제 구현에 대해 생각해보자.

 

주어진 Edges를 이용해 Map<Integer, int[]> 형태의 key-value를 만들어 낼거다.

- key: 해당 노드의 번호

- value: 길이가 2인 배열

   - value[0] : key번 노드에서 나가는 간선 갯수

   - value[1] : key번 노드로 들어오는 간선 갯수

 

이렇게 만든 Map의 keySet을 순회하여 앞서 언급한 그래프들의 조건에 맞는 노드의 갯수를 센다. 조건에 맞지 않는 노드들은 분기에서 지나치기 때문에 같은 그래프가 중복되어 더해질 일은 발생하지 않는다.

 

코드

import java.util.HashMap;
import java.util.Map;

public class Solution {

    private Map<Integer, int[]> graph;

    public int[] solution(int[][] edges) {
        int[] answer = {0, 0, 0, 0};

        graph = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            int from = edges[i][0];
            int to = edges[i][1];

            countToGraph(from, 0);
            countToGraph(to, 1);
        }

        int[] counts;
        for(Integer key : graph.keySet()) {
            counts = graph.get(key);

            if (counts[0] >= 2 && counts[1] == 0) { // 나가는 간선은 2개 이상 있는데 들어오는 간선 0개 -> 생성된 정점
                answer[0] = key;
            } else if (counts[0] == 0 && counts[1] > 0) { // 들어오는 간선은 있는데 나가는 간선이 없는 경우 -> 막대 그래프
                answer[2]++;
            } else if (counts[0] >= 2 && counts[1] >= 2) { // 나가는 간선, 들어오는 간선이 2개 이상인 경우 -> 8자 그래프
                answer[3]++;
            }
        }

        // 생선된 정점에 연결된 노드 갯수(=총 그래프 갯수)에서 막대와 8자 그래프 갯수를 뺌
        answer[1] = graph.get(answer[0])[0] - answer[2] - answer[3];

        return answer;
    }

    private void countToGraph(int node, int code) { // code = 0 : 나가는 것, 1 : 들어오는 것
        int[] counter = graph.getOrDefault(node, new int[] {0, 0}); // 배열[0] : 해당 노드에서 나간 갯수, 배열[1] : 해당 노드에 들어온 갯수
        counter[code]++;
        graph.put(node, counter);
    }
}

 

 

도움받은 링크

[Programmerse] Level2 도넛과 막대 그래프