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

도넛, 막대, 8자 모양의 그래프 종류가 2개 이상 있고, 정점 하나를 새로 생성해서 해당 정점에서 나머지 그래프의 아무 정점으로 이어지는 간선을 추가했을 때, 몇 번 정점이 추가된 것이고, 그래프는 종류별로 몇 개씩 있는지 맞추는 문제이다.

Python

from collections import defaultdict

def solution(edges):
    answer = [0, 0, 0, 0]
    
    ine = defaultdict(list)
    oute = defaultdict(list)
    nodes = set()
    
    for a, b in edges:
        oute[a].append(b)
        ine[b].append(a)
        nodes.add(a)
        nodes.add(b)
    
    # 추가한 정점에서 다른 그래프로 향하는 간선들, 최소 두 개의 그래프 => 추가한 정점은 최소 두 개 이상의 나가는 간선만 있음
    target = None
    for n in nodes:
        if not ine[n] and len(oute[n]) >= 2:
            target = n
    
    # 나가는 간선과 연결된 정점을 기준으로 탐색 시작하기
    roots = oute[target]
    answer[0] = target
    
    for r in roots:
        answer[chkType(oute, ine, r)] += 1
        
    return answer

# 모든 노드가 out 하나 in하나이고 사이클이면 도넛 사이클이 아니면 막대, 정점 하나가 in2, out2면 8자
def chkType(oute, ine, root):
    type = 2 # 1: 도넛, 2: 막대, 3: 8
    que = [root]
    idx = 0
    visited = set()
    visited.add(root)
    
    while idx < len(que):
        now = que[idx]
        idx += 1
        
        if len(oute[now]) + len(ine[now]) >= 4:
            return 3
        
        for next in oute[now]:
            if next in visited:
                type = 1
            else:
                que.append(next)
                visited.add(next)
    return type     

새로 만든 정점 찾기

새로 생성된 정점은 해당 정점에서 나머지 그래프로 향하는 간선만 있기 때문에 만약 오는 간선이 없고 나가는 간선만 2개 이상인 정점을 찾으면 새로 만든 정점을 찾을 수 있다.

그래프 모양 찾기

먼저 8자 모양 그래프는 8자의 가운데 부분에 있는 정점은 무조건 나가는 것 2, 들어오는 간선 2가 있기 때문에 총 간선이 4개이고, 새로 만든 정점과 연결된다면 5개의 간선을 갖게 된다. 그래서 그래프 탐색을 하면서 간선이 4개 이상인 정점이 있다면 해당 그래프는 8자로 식별하였다.

막대와 도넛모양은 사이클의 유무로 판단하였다. 사이클이 없다면 막대이고 사이클이 있다면 도넛으로 식별했다. 그래서 BFS 돌면서 visited에서 한 번 걸린다면 사이클로 판단시켰고, 8자 일수도 있기에 BFS가 끝날 때까지 기다렸다.

Java

import java.util.*;

class Solution {
    public int[] solution(int[][] edges) {
        int[] answer = {0, 0, 0, 0};
        
        Set<Integer> nodes = new HashSet<>();
        Map<Integer, ArrayList<Integer>> out = new HashMap<>();
        Map<Integer, ArrayList<Integer>> in = new HashMap<>();
        
        for(int[] e: edges){
            nodes.add(e[0]);
            nodes.add(e[1]);
            
            if(!out.containsKey(e[0])){
                out.put(e[0], new ArrayList<>());
            }
            if(!in.containsKey(e[1])){
                in.put(e[1], new ArrayList<>());
            }
            
            out.get(e[0]).add(e[1]);
            in.get(e[1]).add(e[0]);
        }
        
        int target = 0;
        
        // 새로 만든 노드 찾기
        for(int n: nodes){
            if(out.containsKey(n) && out.get(n).size() >=2 && !in.containsKey(n)){
                target = n;
            }
        }
        
        answer[0] = target;
        
        // 노드 찾았으면 각 그래프 루트 기준으로 탐색하기
        for(int r: out.get(target)){
            answer[graphType(out, in, r)]++;
        }
        
        return answer;
    }
    
    public int graphType(Map<Integer, ArrayList<Integer>> out, Map<Integer, ArrayList<Integer>> in, int root){
        // 도넛: 1, 막대: 2, 8자: 3
        ArrayList<Integer> que = new ArrayList<>();
        que.add(root);
        int idx = 0;
        Set<Integer> visited = new HashSet<>();
        visited.add(root);
        int type = 2;
        
        while(idx < que.size()){
            int now = que.get(idx++);
            
            if(out.containsKey(now) && in.containsKey(now) && out.get(now).size() + in.get(now).size() >= 4){
                return 3;
            }
            
            if(!out.containsKey(now)){
                continue;
            }
            
            for(int next: out.get(now)){
                if(visited.contains(next)){
                    type = 1;
                } else {
                    que.add(next);
                    visited.add(next);
                }
            }
        }
        
        return type;
    }
}

HashMap이랑 HashSet을 코딩테스트하면서 처음 사용해보았고 메서드도 익숙하지 않아서 IntelliJ의 도움을 많이 받았다.