258711. 도넛과 막대 그래프

문제

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

프로그래머스

제한사항

풀이

1. indegree, outdegree 맵을 초기화한다.

2. 각 그래프 패턴을 특정하는 노드는 확인 후 그래프 패턴 개수를 더한다.

3. 더 중요한 핵심은 그래프 패턴을 특정하는 노드 외에는 그냥 넘길 수 있다는 것을 눈치채는 것이라 생각한다.

import java.util.*;

class Solution {
    public int[] solution(int[][] edges) {
        int[] answer = {};
        // Map<Integer, List<Integer>> graph = new HashMap<>();
        Map<Integer, Integer> outdegree = new HashMap<>();
        Map<Integer, Integer> indegree = new HashMap<>();
        
        int center = -1;
        int eightPattern = 0;
        int barPattern = 0;
        int donutPattern = 0;
        
        
        for(int[] edge : edges) {
            int from = edge[0]; 
            int to = edge[1];
        
            // graph.putIfAbsent(from, new ArrayList<>());
            // graph.get(from).add(to);
            outdegree.put(from, outdegree.getOrDefault(from, 0) + 1);
            indegree.put(to, indegree.getOrDefault(to, 0) + 1);
        }
        
        for(int node : indegree.keySet()) {
            if(!outdegree.containsKey(node) && indegree.get(node) >=1)
                barPattern++; 
        }
        
        for(int node : outdegree.keySet()) {
            if(outdegree.get(node)>=2 && !indegree.containsKey(node))
                center = node;
            else if(outdegree.get(node)>=2 && indegree.get(node)>=2)
                eightPattern++;
            
        }

        
        donutPattern = outdegree.get(center) - (eightPattern + barPattern);
        
        answer = new int[]{center, donutPattern, barPattern, eightPattern};
        
        return answer;
    }

}

회고

그래프를 잇는 중심이 되는 정점을 찾고, 각 그래프 패턴의 개수를 찾는 문제였다. 처음에 이 문제를 풀 때는 중심 정점을 찾고, 중심 정점 기준으로 간선이 있는 그래프를 탐색한다. 각 그래프의 정점들을 돌면서 어떤 그래프 패턴인지 찾으려고 했다. 구현하는데 매우 힘들었고 결국 풀지 못했다. 

풀이를 보니 무릎을 탁 칠수 밖에 없었다. 풀이에서는 중심 정점도 일종의 그래프 패턴처럼 취급하고 모든 노드를 돌면서 중심 정점 또는 그래프 패턴을 찾는다. 조건은 아래와 같다.

• 중심 정점은 밖 간선만 있고 안 간선은 없다.
• 막대기 패턴은 안 간선은 있지만 밖 간선은 없다.
• 8자 패턴은 안 간선 2개 이상, 밖 간선 2개 이상이다.
• 도넛 패턴은 그래프 개수에서 (막대기 패턴 + 8자 패턴) 개수를 빼면 된다.
• 모든 그래프 개수는 중심 정점의 밖 간선 개수와 같다.

여기서 더 중요한 핵심은 모든 노드를 탐색하면서 그래프 패턴을 판단할 수 없는 노드는 넘기는 것이다. 그래프의 노드들 중 그래프의 패턴을 특정할 수 있는 노드는 반드시 존재한다. 그 노드 외에는 그냥 넘기면 되는 논리가 인상 깊었다.