[프로그래머스] LV.2 도넛과 막대 그래프 (JAVA)

문제 - 도넛과 막대 그래프

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

접근 방식

각 노드에서 나오는 간선의 개수로 그래프를 나눠 카운트를 올리는 방식

처음 이문제를 접근할 때 , 각 노드를 연결하고 탐색해야 한다고 생각했다.
그래서 처음 짰던 코드는 bfs를 사용해서
Queue가 비었을 경우 : 막대그래프
들어오는 간선과 나가는 간선이 두개인 경우 : 8자 그래프
간선이 두개인 노드를 발견하지 못하고, 자기자신으로 돌아온 경우 : 도넛 그래프
로 구분하였고 다음과 같다.

public static void findGraph(int start){
        int cnt = 0;
        int [] visited = new int [N+1];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start]++;
        while(!queue.isEmpty()){
            int now = queue.poll();
            if(start==now&&cnt!=0) {
                donutCnt++;
                return;
            }
            if(map.get(now)==null) continue;
            for(int i : map.get(now)){
                if(inOut[i][0]>1 && inOut[i][1]>1) {
                    eightCnt++;
                    return;
                }

                queue.add(i);
                visited[i]++;
                cnt++;
            }

        }
        stickCnt++;
        return;
        
    }

하지만 테스트9에서 계속 시간초과가 발생하였고, 어떻게 해야 시간 복잡도를 줄일 수 있을까 고민을 하다, 8자와 도넛의 차이가 간선의 개수라는 생각이 들면서 모든 그래프를 간선의 갯수로 표시할 수 있지 않을까 라고 생각했다.

결론적으로 내가 분류한 기준은

들어오는 간선은 없지만 나가는 간선은 1개 이상인 노드 : 생성된 정점
나가는 간선이 2개인 노드 : 8자 그래프 중 가운데 노드
들어오는 간선이 1개 이상이지만 나가는 간선이 없는 노드 : 막대 그래프의 마지막 노드

였다.
그래서 HashMap으로 각 노드의 연결된 노드를 구해놓고
생성된 정점과 이어진 노드의 수 (= 전체 그래프 수) - 8자 그래프 수 - 막대 그래프 수 = 도넛 그래프 로 세웠다.

정답코드

import java.util.*;

class Solution {
    static int donutCnt =0, stickCnt =0, eightCnt =0, circle = 0;
    static int [][] inOut;
    static int N;
    static HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
    public static int[] solution(int[][] edges) {
        

        for(int i =0; i<edges.length;i++){
            if(map.get(edges[i][0])!=null){
                ArrayList<Integer> result = map.get(edges[i][0]);
                result.add(edges[i][1]);
                map.put(edges[i][0],result);
            }
            else{
                ArrayList<Integer> result =new ArrayList<>();
                result.add(edges[i][1]);
                map.put(edges[i][0], result);
            }
                
        }
        HashSet<Integer> nodes = new HashSet<>();
        for(int i =0;i<edges.length;i++){
            nodes.add(edges[i][0]);
            nodes.add(edges[i][1]);
        }
        N = nodes.size();
        inOut = new int [N+1][2];
        for(int i =0;i<edges.length;i++){
            inOut[edges[i][0]][0] ++;
            inOut[edges[i][1]][1] ++;
            
        }
        for(int i=0;i<inOut.length;i++){
            if(inOut[i][1]==0 &&inOut[i][0]>1) circle = i;
        }
        inOut[circle][1]= -1;
        inOut[circle][0] = -1;
        
        for(int i=0;i<inOut.length;i++){
            if(inOut[i][0]==2) eightCnt++;
            else if(inOut[i][1]>0 && inOut[i][0]==0) stickCnt++;
        }
        donutCnt = map.get(circle).size()-eightCnt-stickCnt;
        int[] answer = {circle, donutCnt, stickCnt, eightCnt};
        return answer;
    }
}

이 문제를 풀며 배운 점

• 분류를 하는 문제라면, 가장 먼저 차이점을 정의하자.
  차이점을 정의한다면 생각보다 쉬운 해결책을 찾을 수도 있다.
• 뭐든지 과정이 필요하다고 생각하지 말자.
  문제를 풀면서 항상 주어진 흐름에 맞춰 구하려고 한다. 하지만 조금도 들여보면, 그 흐름보다 쉬운 방법을 찾을 수도 있다 !!