프로그래머스/자바 Lv2

[프로그래머스] Java Lv2. 코딩테스트 연습 > 2024 KAKAO WINTER INTERNSHIP > 도넛과 막대 그래프

행수쌤 2024. 11. 30. 17:49
728x90
반응형

문제설명

  • 크기가 n인 도넛 모양 그래프는 n개의 정점과 n개의 간선이 있다.
  • 아무 한 정점에서 출발해 이용한 적 없는 간선을 계속 따라가다 보면 n-1개의 정점들을 한 번 씩 방문 뒤 원래 정점으로 돌아온다.

  • 크기가 n인 막대 모양 그래프는 n개의 정점과 n-1개의 간선이 있다.
  • 임의의 한 정점에서 출발해 간선을 계속 따라가면 나머지 n-1개의 정점을 한 번씩 방문하게 되는 정점이 단 하나 존재한다.

  • 크기가 n인 8자 모양 그래프는 2n+1개의 정점과 2n+2개의 간선이 있다.
  • 크기가 동일한 2개의 도넛 모양 그래프에서 정을 하나씩 골라 결합한 형태이다.

  • 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프가 여러개 있다.
  • 이 그래프들과 무관한 정점을 하나 생성 한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했다.
  • 그래프의 간선 정보가 주어지면 생성한 정점의 번호와 정점을 생성하기 전 도넛 모양 그래프 수, 막대 모양 그래프 수, 8자 모양 그래프 수를 구해야 한다.

제한사항

  • 1 <= edges의 길이 <= 1,000,000
  • 그래프의 수의 합은 2 이상

접근방법

  1. 뭐니뭐니해도 가장 어려운 일이지만 코드를 짜기 전에 문제를 잘 이해해야 한다. 생성 정점을 잘못 이해하고 코드 먼저 짰다가 코드 완전히 다시 짬..
  2. '이 그래프들과 무관한 정점을 하나 생성 한 뒤' -> 생성 정점은 도넛, 막대, 8자 그래프가에 포함되는게 아니라 단 하나 독립적으로 존재하여 각각의 그래프로 뻗어나가는 간선만 존재한다.
  3. 각 그래프간에 간선으로 연결되어 있지 않으므로, 생성 정점에서 간선을 통해 한 정점에 도달하면, 그 정점이 어떤 그래프에 포함된 놈인지만 판단하면 된다.
  4. 생성 정점을 먼저 파악하는게 좋아보인다. 생성 정점을 어떻게 알 수 있을까? 우선 모든 간선이 밖으로 나가는 놈이다. 모든 간선이 밖으로 나가는 놈이 생성 정점밖에 없을까? 막대 그래프의 가장 아래 정점일 가능성이 있으나 그래프의 합은 2 이상이므로 생성 정점에서 나가는 노드는 최소 2개이다.
  5. 생성 정점에서 온 간선을 제외하고 각 그래프에서 간선을 따라 정점들을 방문하면서 그래프의 특성을 파악한다.
    1. 직선 그래프는 정점에서 나가는 간선이 없는 정점이 발견된다.
    2. 8자 그래프는 정점에서 나가는 간선이 2개인 정점이 발견된다.
    3. 도넛 그래프는 방문했던 정점을 다시 방문하게 된다.

핵심로직

  1. 정점의 개수를 파악한다.
  2. 그래프 초기화 => 정점(index) 에서 밖으로 나가는 간선을 담는 리스트와 정점으로 들어오는 간선의 수를 카운트 하는 리스트를 생성한다.
  3. 생성 정점 탐색 => 정점을 돌면서 나가는 간선이 2개 이상이고 들어오는 간선은 없는 정점을 찾는다.
  4. 그래프 분리 => 생성 정점의 간선을 따라 도착한 정점들의 들어오는 간선 수 카운트를 -1 해준다.
  5. 그래프 파악 => 분리된 각각의 그래프를 돌면서 그래프의 특징에 따라 그래프 카운트를 해준다.
    1. 직선 그래프는 정점에서 나가는 간선이 없는 정점이 발견된다.
    2. 8자 그래프는 정점에서 나가는 간선이 2개인 정점이 발견된다.
    3. 도넛 그래프는 방문했던 정점을 다시 방문하게 된다.(Queue 사용)

입출력 예

  • edges = [[2, 3], [4, 3], [1, 1], [2, 1]]
  • result = [2, 1, 1, 0]

코드 작성

import java.util.*;

class Solution {
    // 전체 정점의 개수 카운트
    private static int nodeCount = 0;
    // 정점(index) 에서의 간선 방향을 담은 리스트
    private static List<List<Integer>> graph = new ArrayList<>();
    // 각 정점으로 들어오는 간선의 개수
    private static List<Integer> entranceCount = new ArrayList<>();
    private static boolean[] visited;
    
    public int[] solution(int[][] edges) {
        int donut = 0;
        int stick = 0;
        int eight = 0;
        // 1. 정점 개수 파악
        for(int i=0; i<edges.length; i++) {
            nodeCount = Math.max(nodeCount, Math.max(edges[i][0], edges[i][1]));
        }
        visited = new boolean[nodeCount+1];
        
        // 2. 그래프 초기화
        for(int i=0; i<=nodeCount; i++) {
            graph.add(new ArrayList<>());
            entranceCount.add(0);
        }
        
        for(int i=0; i<edges.length; i++) {
            graph.get(edges[i][0]).add(edges[i][1]);
            entranceCount.set(edges[i][1], entranceCount.get(edges[i][1]) +1);
        }
        
        // 3. 생성 정점 탐색
        int startNum = findStartNum();
        
        List<Integer> startWay = graph.get(startNum);
        
        // 4. 그래프 분리
        for(int i=0; i<startWay.size(); i++) {
            entranceCount.set(startWay.get(i), entranceCount.get(startWay.get(i)) -1);
        }
        
        // 5. 그래프 파악
        for(int i=0; i<startWay.size(); i++) {
            int node = startWay.get(i);
            Queue<Integer> numQ = new LinkedList<>();
            while(true) {
                if(graph.get(node).size() == 2 && entranceCount.get(node) == 2) {
                    eight ++;
                    break;
                } else if(graph.get(node).size() == 0) {
                    stick ++;
                    break;
                } else {
                    for(int j=0; j<graph.get(node).size(); j++) {
                        if(!visited[graph.get(node).get(j)]) {
                            numQ.add(graph.get(node).get(j));
                            visited[graph.get(node).get(j)] = true;
                        }
                    }
                    if(numQ.size() > 0) {
                        node = numQ.poll();
                    } else {
                        donut ++;
                        break;
                    }
                }
            }
        }
        
        return new int[]{startNum, donut, stick, eight};
    }
    
    // 3. 생성 정점 탐색
    private static int findStartNum() {
        int index = -1;
        for(int i=1; i<=nodeCount; i++) {
            if(graph.get(i).size() >= 2 && entranceCount.get(i) == 0) {
                index = i;
                break;
            }
        }
        return index;
    }
}

정답을 맞추긴 했지만 가독성이 다소 떨어지고 도넛 그래프 파악을 위한 Queue의 사용이 조금 애매하다. Queue를 사용해 도넛그래프를 파악하는 개념은 유지하되, queue가 빈 상태에서 그래프 파악이 안 됐다면 도넛 그래프임이 확실하므로, while(true)를 while(!queue.isEmpty())로 바꿔준다.

코드 작성(2차)

import java.util.*;

class Solution {
    private static int nodeCount = 0; // 전체 정점의 개수
    private static List<List<Integer>> graph = new ArrayList<>(); // 각 정점의 간선 정보
    private static List<Integer> entranceCount = new ArrayList<>(); // 각 정점으로 들어오는 간선의 개수
    private static boolean[] visited; // 방문 여부

    public int[] solution(int[][] edges) {
        int donut = 0, stick = 0, eight = 0;

        // 1. 정점 개수 파악
        for (int[] edge : edges) {
            nodeCount = Math.max(nodeCount, Math.max(edge[0], edge[1]));
        }
        visited = new boolean[nodeCount + 1];

        // 2. 그래프 초기화
        for (int i = 0; i <= nodeCount; i++) {
            graph.add(new ArrayList<>());
            entranceCount.add(0);
        }

        // 3. 간선 정보 입력
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            entranceCount.set(edge[1], entranceCount.get(edge[1]) + 1);
        }

        // 4. 생성 정점 탐색
        int startNum = findStartNum();
        List<Integer> startWay = graph.get(startNum);

        // 5. 생성 정점과 연결된 정점의 간선 제거
        for (int node : startWay) {
            entranceCount.set(node, entranceCount.get(node) - 1);
        }

        // 6. 그래프 파악
        for (int node : startWay) {
            if (!visited[node]) {
                int type = exploreGraph(node);
                if (type == 0) donut++;
                else if (type == 1) stick++;
                else if (type == 2) eight++;
            }
        }

        return new int[]{startNum, donut, stick, eight};
    }

    // 생성 정점 탐색
    private static int findStartNum() {
        for (int i = 1; i <= nodeCount; i++) {
            if (graph.get(i).size() >= 2 && entranceCount.get(i) == 0) {
                return i;
            }
        }
        return -1;
    }

    // 그래프 탐색 및 유형 판별
    private static int exploreGraph(int startNode) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(startNode);
        visited[startNode] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (graph.get(node).size() == 2 && entranceCount.get(node) == 2) {
                return 2; // 8 형태
            } else if (graph.get(node).isEmpty()) {
                return 1; // 막대 형태
            } else {
                for (int neighbor : graph.get(node)) {
                    if (!visited[neighbor]) {
                        queue.add(neighbor);
                        visited[neighbor] = true;
                    }
                }
            }
        }
        return 0; // 도넛 형태
    }
}

 

728x90
반응형