2024 KAKAO WINTER INTERNSHIP - 도넛과 막대 그래프 <JAVA>

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

프로그래머스

 

문제 

 

 

1. 막대 모양 그래프

2. 8자 모양 그래프

3. 도넛 모양 그래프

4. 루트 정점 

 

-> 구해야하는 항목들이다 

 

 

 

처음엔 dfs, bfs 를 떠올렸다 각각 모양의 그래프를 체크하고 ? 루트도 찾고 ? 싸이클도 찾고? 좀 머리가 지근거렸다.

 

웃기긴한데 좀 카카오스럽게? 빡구현인가? 방향 그래프네? 진출 차수? 진입 차수? 로 생각을 하다보니 

 

그래프 별로 진출 차수 ,진입 차수의 규칙이 하나씩 보이기 시작했다.

 

규칙 1 . 

      루트 정점 : 진입 차수 - 0 개 , 진출 차수 - 2개 이상

      막대 그래프 : 진입 차수 - 1개 , 진출 차수 - 0 개

     8자 그래프 : 진입 차수 - 2개 이상 , 진출 차수 - 2개 이상

 

사실 사이클 구하기가 너무 싫었다 ㅋㅋ..  입출력 예시를 보면 ? --> 루트 정점으로 부터 그래프가 뻗어 나온다 

즉?

 

도넛그래프 수 =  루트 정점의 진출 차수 개수 - (막대 그래프 수 + 8자 그래프 수) 

 

 

정답 코드

// 이때 당신은 그래프의 간선 정보가 주어지면 
// 생성한 정점의 번호와 
// 정점을 생성하기 전 도넛 모양 그래프의 수,
// 막대 모양 그래프의 수, 
// 8자 모양 그래프의 수를 구해야 합니다.
import java.util.*;

class Solution {
    public int[] solution(int[][] edges) {
        int[] answer = new int[4];
        //정점번호, [진출차수 , 진입차수] 저장할 Map 선언
        HashMap<Integer, int[]> map = new HashMap<>();
        //맵 초기화
        for(int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            
            if(!map.containsKey(from)) {
                map.put(from,new int[] {0,0});
            }
            if(!map.containsKey(to)) {
                map.put(to,new int[] {0,0});
            }
            
            // 시작 정점의 진출 차수를 1더해준다
            map.get(from)[0]++;
            // 도착 정점의 진입 차수를 1더해준다
            map.get(to)[1]++;
        }
        //1번 노드 부터 제일 큰 노드번호 까지 순회
        for(int i=1; i<=map.size(); i++) {
            if(map.get(i)[0] >= 2 && map.get(i)[1] == 0) {
                answer[0] = i; //루트 정점 노드번호 삽입
            }
            else if(map.get(i)[0] == 0) { //막대 그래프 -> 해당 노드 i의 진출 차수가 0이라면 
                answer[2]++;
            }
            else if(map.get(i)[0] >= 2 && map.get(i)[1] >= 2) { // 8자 모양 그래프수 -> 진입차수 2개 이상, 진출차수 2개 이상
                answer[3]++;
            }
        }
        //전체 그래프수 -> 생성 정점의 진출 차수 - (막대 모양 그래프 수 + 8자 모양 그래프 수)
        answer[1] = map.get(answer[0])[0] - (answer[2] + answer[3]);
        // 루트 정점 , 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수
        return answer;
    }
}