도넛과 막대 그래프 [JAVA]

문제분석

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

프로그래머스

단방향 edge들이 최대 100만개 주어진다.

각 edge들은 도넛, 막대, 8자형 그래프 중 하나를 구성한다.

단, 하나의 노드가 이 그래프와 무관하게 생성되어 있고 이 노드로 부터 각 그래프로의 간선이 추가되어 있다.

이때, 해당 노드의 번호와 전체 그래프의 수를 종류별로 구해주면 되는 문제다.

 

언뜻보면 꽤 복잡하지만, 우리가 찾아야 하는 무관하게 생성된 노드는 해당 노드에서 다른 노드로의 간선만 존재한다는 특징이 있다.

 

따라서, key 노드로 향하는 간선의 정보를 담는 Map, key 노드에서 나가는 방향의 간선들의 정보를 담는 Map 두 가지 맵을 생성하여 간선 정보를 저장해주고

 

전체 노드들에 대해서 나가는 방향의 간선만 존재하는 경우만 있는 노드가 우리가 찾던 무관하게 추가된 노드라는 뜻이 된다.

(단, 막대형 그래프의 시작 노드의 경우에도 해당 노드에서 나가는 방향의 노드만 존재하기에 이를 주의해야 한다.)

• 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다.

(문제엔 이런 조건이 있다, 막대형 그래프의 시작 노드는 나가는 방향 간선이 항상 1이기에 이를 만족하지 못한다. 이를 이용해서 막대형 그래프의 시작노드인 경우 skip 하여 우리가 찾는 추가된 노드를 대상으로 탐색을 시작할 수 있다.)

 

이제 추가된 노드에서 나가는 방향의 간선으로 연결된 각 노드들은 3가지 그래프 중 하나의 구성원이라는 뜻이 된다.

 

여기서, 연결된 노드로 들어오는 방향 간선의 수를 기준으로 그래프를 판단할 수 있다.

1인 경우, 막대형 그래프의 시작 노드만 해당되기에 막대 그래프의 수를 증가시키면 된다.

3이상인 경우, 8자형 그래프의 중앙 노드만 해당되기에 8자형 그래프의 수를 증가시키면 된다.

 

2인 경우 3가지 모두 가능하다.

따라서, 연결된 노드(link) 부터 순차적으로 다음 노드(nowLink)를 찾아가며 확인해봐야 한다. 탐색 중 가능한 경우의 수는 아래와 같다.

 

다음 노드가 없는 경우 -> 막대

현재 탐색 노드(nowLink)에서 나가는 방향 간선의 수가 1이고 연결된 다음 노드가 시작 노드 (link)인 경우 -> 도넛

현재 탐색 노드(nowLink)에서 나가는 방향 간선의 수가 2이상인 경우 -> 8자형 (8자형의 중앙 노드만 이 조건을 만족한다.)

 

이렇게 각 그래프의 수를 계산한 뒤 정답 배열에 저장해서 리턴해주면 된다.

 

코드

import java.util.*;

class Solution {
    public int[] solution(int[][] edges) {
        int[] answer = new int[4];
        // x to Key
        Map<Integer, Set<Integer>> toKey = new HashMap<>();
        // Key to X
        Map<Integer, Set<Integer>> fromKey = new HashMap<>();
        
        Set<Integer> nodes = new HashSet<>();
        for(int i=0; i<edges.length; i++){
            nodes.add(edges[i][0]);
            nodes.add(edges[i][1]);
            
            if(!fromKey.containsKey(edges[i][0]))
                fromKey.put(edges[i][0], new HashSet<>());
            if(!toKey.containsKey(edges[i][1]))
                toKey.put(edges[i][1], new HashSet<>());
            
            fromKey.get(edges[i][0]).add(edges[i][1]);
            toKey.get(edges[i][1]).add(edges[i][0]);
        }
        
        //all graph sum is more than 2
        
        for(int target : nodes){
            if(toKey.containsKey(target))
                continue;
            if(!fromKey.containsKey(target))
                continue;
            
            //target is not the unique, have to contain all nodes.
            //target can be start node of stick
            // but graph sum is more than 2
            if(fromKey.get(target).size() < 2)
                continue;
            
            answer[0] = target;
            
            int doughnut = 0;
            int stick = 0;
            int eight = 0;
            for(int link : fromKey.get(target)){
                
                Set<Integer> toLinks = toKey.get(link);
                if(toLinks.size() == 1){
                    // start node at stick is the only case
                    int nowLink = link;
                    stick++;
                    
                }else if(toLinks.size() == 2){
                    //except target there is another one link
                    //all case is possible
                    
                    int nowLink = link;
                    
                    while(true){
                        if(!fromKey.containsKey(nowLink)){
                            //it is stick
                            stick++;
                            break;
                        }
                        
                        Set<Integer> fromNowLink = fromKey.get(nowLink);
                        if(fromNowLink.size() == 1){
                            boolean isDoughnut = false;
                            for(int next : fromNowLink){
                                if(next == link){
                                    //made cycle -> doughnut
                                    doughnut++;
                                    isDoughnut = true;
                                }else{
                                    nowLink = next;
                                }
                            }
                            if(isDoughnut)
                                break;
                        }else{
                            eight++;
                            break;
                        } 
                    }
                }else{
                    //have to be eight
                    eight++;
                }
            }
            
            answer[1] = doughnut;
            answer[2] = stick;
            answer[3] = eight;
            break;
        }
        
        return answer;
    }
}