프로그래머스 - 도넛과 막대 그래프(Java)

By on January 7, 2024

프로그래머스 - 도넛과 막대 그래프(Java)

프로그래머스 - 도넛과 막대 그래프 문제는 주어진 그래프에서 정점과 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프를 찾는 문제 입니다.

처음에는 그래프 순회 알고리즘을 사용해서 도넛과 막대를 찾고 유니온 파인드를 사용해서 순환그래프를 찾으려 했었습니다…..(반성)

그런데 edge 의 길이가 1,000,000…….문제 풀이 힌트를 좀 참고해서 풀고 규칙을 이해 했습니다. (반성2)

문제 해결 접근법

문제를 해결하기 위한 접근 방법은 다음과 같습니다.

  • 그래프 생성: 주어진 간선 정보를 바탕으로 그래프를 생성합니다. 정점은 나가는 간선만 있고 받는 간선은 없습니다. 각 정점의 나가는 간선 수와 받는 간선 수를 세어서 저장합니다.

  • 정점, 막대, 8자 구분, 도넛

    • 정점은 받는 간선이 2개 이상이고 나가는 간선이 없는 경우입니다.
    • 막대는 받는 간선이 없는 경우입니다.
    • 8자는 나가는 간선이 2개 이상이고 받는 간선도 2개 이상인 경우입니다.
    • 나머지 경우는 도넛입니다. 도넛의 경우 정점의 간선에서 막대 수와 8자 수를 제외한 나머지입니다.

소스

public class PG_258711 {
    public int[] solution(int[][] edges) {
        int[] answer = new int[4];

        int maxNum = 0; //정점의 개수
        Map<Integer, Edge> graph = new HashMap<>();

        for(int i = 0 ; i < edges.length; i++){
            int giveNum = edges[i][0];
            int receiveNum = edges[i][1];

            if(maxNum < giveNum) maxNum = giveNum;
            if(maxNum < receiveNum) maxNum = receiveNum;

            if(!graph.containsKey(giveNum)) graph.put(giveNum, new Edge(0, 0));
            if(!graph.containsKey(receiveNum)) graph.put(receiveNum, new Edge(0, 0));

            graph.get(giveNum).giveCount++;
            graph.get(receiveNum).receiveCount++;
        }

        for(int i = 1; i <= maxNum; i++){
            int giveCount = graph.get(i).giveCount;
            int receiveCount = graph.get(i).receiveCount;

            if(giveCount >= 2 && receiveCount == 0){
                //정점 : 받는 간선이 2개 이상 이고 나가는 간선이 없다(0)
                answer[0] = i;
            }else if(graph.get(i).giveCount == 0){
                //막대 : 받는 간선이 없이 나가는 간선만 있음.
                answer[2]++;
            }else if(graph.get(i).giveCount >= 2 && graph.get(i).receiveCount >= 2){
                //8자 : 받고 나가는 간선이 2개 이상 이어야 한다.
                answer[3]++;
            }

        }
        // 도넛
        answer[1] = graph.get(answer[0]).giveNum - answer[2] - answer[3];
        return answer;
    }

    public class Edge {
        private int giveCount;
        private int receiveCount;
        public Edge(int giveCount, int receiveCount) {
            this.giveCount = giveCount;
            this.receiveCount = receiveCount;
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "giveCount=" + giveCount +
                    ", receiveCount=" + receiveCount +
                    '}';
        }
    }
}

코드 설명

그래프 생성: graph 맵을 사용하여 정점의 나가는 간선 수(giveCount)와 받는 간선 수(receiveCount)를 저장합니다.

정점, 막대, 8자 구분: 그래프를 순회하면서 정점, 막대, 8자를 찾습니다.

도넛 찾기: 나머지 경우는 도넛으로 판별하고, 도넛의 경우 정점의 간선에서 막대 수와 8자 수를 제외한 나머지입니다.

마무리

이러한 방식으로 주어진 그래프에서 정점, 막대, 8자, 도넛을 찾는 문제를 해결할 수 있습니다.
주어진 규칙을 이해하고 그에 맞게 간선 수를 세어 나가는 것이 핵심입니다. 코드는 각 정점에 대한 간선 수를 계산하고,
그에 따라 정점, 막대, 8자, 도넛을 판별하여 결과를 반환합니다.

Back to blog