[프로그래머스/Level2] 도넛과 막대 그래프 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• 구현 (배열)

총 2가지의 배열 (진입/진출 간선 수 저장용 배열)을 생성한다.

각 그래프 모양마다 진입 간선 수와 진출 간선 수에서 어떤 특징을 갖는지에 따라 갯수를 구한다.

- 생성점         → 진입 간선 X / 진출 간선 수 >= 2           인 정점
- 막대 그래프 → 진입 간선 수 = 1 / 진출 간선 X             인 정점
- 8자 그래프   → 진입 간선 수 >= 2 / 진출 간선 수 >= 2  인 정점
- 도넛             → 막대와 8자 그래프를 제외한 나머지

 

 

💥 유의사항

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static final int MAX = 1_000_000;
    
    static int[][] edges;
    static int[] input, output;
    
    public int[] solution(int[][] edges) {
        this.edges = edges;
                        
        input = new int[MAX + 1];   // 받은 것 (진입)
        output = new int[MAX + 1];  // 준 것   (진출)
        
        int maxNode = 0;
        for(int[] e : edges) {
            input[e[1]]++;
            output[e[0]]++;
            
            maxNode = Math.max(maxNode, Math.max(e[0], e[1]));
        }
        
        int[] answer = new int[4];
               
        for(int i = 1 ; i <= maxNode ; i++) {
            if(input[i] == 0 && output[i] >= 2) {   // [정점] 진입 간선이 없고, 진출 간선이 2개 이상인 경우
                answer[0] = i;
            }
            else if(input[i] > 0 && output[i] == 0) {   // [막대 모양] 진입 간선이 1개 이상, 최상위 노드에서 다른 노드로 진출하는 간선이 없는 경우
                answer[2]++;
            }
            else if(input[i] >= 2 && output[i] >= 2) {  // [8자 모양] 진입 간선이 2개 이상, 진출 간선이 2개 이상인 경우
                answer[3]++;
            }
        }
        
        // [도넛 모양] 생성된 정점으로부터 진출한 간선 수 - (막대 모양 그래프 수 + 8자 모양 그래프 수)
        answer[1] = output[answer[0]] - (answer[2] + answer[3]);
        
        return answer;
    }
}
 

 

 

➕ 다른 풀이 방식

1) Map을 활용한 풀이

[Programmerse] Level2 도넛과 막대 그래프

 

 

2) 사이클의 갯수를 구해 모양을 판별하는 풀이다. (BFS)

사이클이 0개면 막대, 사이클이 2개면 8자, 그 외의 경우면 도넛 모양으로 처리한다.

(내가 처음에 풀려고 생각했던 방식!!!)

import java.util.*;
 
class Solution {
    static final int L = 1000000;
 
    List<Integer>[] adjList = new ArrayList[L + 1];
 
    int[] outDegree = new int[L + 1];
    int[] inDegree = new int[L + 1];
    boolean[] isVisited = new boolean[L + 1];
 
    public int[] solution(int[][] edges) {
        for (int i = 0 ; i <= L ; i++) {
            adjList[i] = new ArrayList<>();
        }
 
        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            adjList[from].add(to);
 
            inDegree[to]++;
            outDegree[from]++;
        }
 
        int start = 0;
        for (int i = 1; i <= L; i++) {
            if (outDegree[i] >= 2 && inDegree[i] == 0) {
                start = i;
                break;
            }
        }
 
        int[] answer = new int[]{start, 0, 0, 0};
        for (int now : adjList[start]) {
            int cycleCount = findCycleCount(now);
 
            if (cycleCount == 0) {    // 막대
                answer[2]++;
            } else if (cycleCount == 2) {    // 8자
                answer[3]++;
            } else {    // 나머지
                answer[1]++;
            }
        }
        return answer;
    }
 
    // ⭐ 사이클 갯수 찾는 메서드 (BFS)
    private int findCycleCount(int s) {
        Deque<Integer> q = new ArrayDeque<>();
        q.add(s);
        isVisited[s] = true;
 
        int cycleCount = 0;
        while(!q.isEmpty()) {
            int now = q.poll();
            for (int next : adjList[now]) {
                if (isVisited[next]) {
                    cycleCount++;
                    continue;
                }
                q.add(next);
                isVisited[next] = true;
            }
        }
 
        return cycleCount; 
    }
}

 

 

---

💦 어려웠던 점

- 35번째 TC만 틀린다면 아래 내용을 확인하면 좋을 것 같다. (나의 경우 29번째 줄 else if문에서 input[i] > 0 이라는 조건을 빠뜨려 틀리고 있었다.)

프로그래머스

 

 

 

🧐 새로 알게 된 내용

- 그림 보고 특징을 잘 파악하자,,,,

- 사이클 갯수 확인하는 방법도 기억해두자... (BFS)

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[프로그래머스] 도넛과 막대 그래프

[Programmers] 도넛과 막대 그래프

 

프로그래머스