[프로그래머] (2024 KAKAO WINTER INTERNSHIP) 도넛과 막대 그래프 / 자바(Java)

문제

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

프로그래머스

 

---

해설

오직 간선들로만 주어진 값들을 이용해 3가지 그래프의 개수와 그래프에 포함되지 않는 노드 하나를 구하는 문제입니다.

처음 문제를 보았을 때 그래프를 순환으로 확인해야 하나 고민이 많았지만 생각의 방법을 바꾸어 찾아야 하는 것들의 특징들을 이용했습니다.

 

찾아야하는 요소는 총 4개 생성한 정점의 번호, 도넛모양그래프의 수, 막대모양 그래프의 수, 8자모양 그래프의 수입니다.

 

 

1. 생성한 정점의 번호

생성한 정점은 그래프들과 무관하게 생성되어 각 그래프의 임의의 한 점으로 향하는 간선들이 있습니다.  즉

정점에서 나가는 간선의 수는 그래프의 총 수 이며 정점으로 들어오는 간선의 수는 항상 0입니다.

 

2. 막대모양 그래프의 수

막대모양 그래프를 구별할 수 있는 유일한 요소는 막대모양 그래프의 가장 마지막 노드입니다. 다른 노드들과는 달리 나가는 간선이 없으며 각 막대모양 그래프 하나당 하나씩만 존재합니다.

 

3. 8자모양 그래프의 수

구별가능한 유일한 요소는 두 도넛모양그래프를 이어주는 중간노드입니다. 나가는 간선이 2개이며 들어오는 간선은 2개이상(생성한 정점에서 간선이 뻗어온다면)이 되며 다른 곳에서는 발견되지 않습니다.

 

4. 도넛모양 그래프의 수

도넛모양 그래프에서 유일한 요소가 되는 노드는 없습니다. 하지만 생성한 정점에서 나가는 간선의 수가 그래프의 총 수라는 것과 다른 그래프의 수를 알고 있으므로 그 차를 이용해 그래프의 수를 구할 수 있습니다.

 

위와같이 원하는 답 4가지는 각 노드별 나가고, 들어오는 간선의 수로 알 수 있었습니다. 따라서 이를 쉽게 알기 위해 Map을 사용합니다 노드 번호를 Key로 쓰고 Value는 int[]배열이며 해당 배열의 [0]은 나가는 간선의 수, [1]은 들어오는 간선의 수로 입력값으로 변환해 줍니다.

 

이후 모든 노드들을 탐색하면서 위의 3 조건에 맞는 경우를 파악하며 답을 구해낼 수 있었습니다.

 

주의점

• 각 그래프의 유일한 특징을 찾아본다.
• 생성한 정점의 특징을 유념한다.

---

코드

import java.util.*;

class Solution {
    public int[] solution(int[][] edges) {
        int[] answer = new int[4];
        
        // conInfo : 노드별로 연결된 간선을 확인하는 map (int배열의 [0]은 나가는 간선, [1]은 들어오는 간선)
        Map<Integer, int[]> conInfo = new HashMap<>();
        
        // 총 노드의 수(가장큰 노드번호를 통해 구한다.)
        int numNode = -1;
        
        // 각 간선별로 들어가는 노드와 나가는 노드에 각각 추가해준다.
        for(int i=0;i<edges.length;i++){
            int[] tmp1 = conInfo.getOrDefault(edges[i][0], new int[2]);
            tmp1[0]++;
            conInfo.put(edges[i][0], tmp1);
            
            int[] tmp2 = conInfo.getOrDefault(edges[i][1], new int[2]);
            tmp2[1]++;
            conInfo.put(edges[i][1], tmp2);
            
            numNode = Math.max(numNode,Math.max(edges[i][0],edges[i][1]));
        }
        
        for(int i=1;i<=numNode;i++){
            
            // 그래프와 무관한 정점 : 들어오는 간선이 없으며 나가는 간선은 2개이상(그래프의 수의 합이 2이상)
            if(conInfo.get(i)[0]>=2 && conInfo.get(i)[1]==0){
                answer[0] = i;
                
            // 막대 그래프의 수 : 마지막 노드는 유일하게 나가는 간선이 없다
            }else if(conInfo.get(i)[0]==0){
                answer[2]++;
                
            // 8자 모양 그래프의 수 : 도넛 모양 그래프 2개의 연결 노드는 그래프당 하나이며 2개이상 나가며 2개이상 들어온다.
            }else if(conInfo.get(i)[0]>=2 && conInfo.get(i)[1]>=2){
                answer[3]++;
            }
        }
        
        // 도넛모양 그래프의 수 : 총 그래프의 수는 그래프와 무관한 정점(answer[0])에 연결된 간선의 수와 같다.
        answer[1] = conInfo.get(answer[0])[0] - answer[2]- answer[3];
        return answer;
    }
}