[lv.2] 도넛과 막대 그래프

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

• 문제
  
  
  
  

• 풀이
  1) 위 그래프들과 무관한 정점, 즉 start를 다음 조건으로 찾는다.
  1. 연결 요소가 2이상
2. 나머지 정점의 연결 요소에 자신이 없음
  2) start에서부터 bfs를 시작하여 그래프들을 다음 조건으로 찾는다.
  도넛 : 이미 방문한 정점에 다시 온 경우
막대 : 방문한 정점에서 더이상 갈 정점이 없는 경우
8자 : 지금 정점에서 연결 요소가 2일 경우

• 소감
  이거 lv2인데 구현에선 얼마 안걸렸지만 방법 찾는데서 1시간을 써버렸다...

• 코드

import java.util.*;

class Solution {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    public int[] solution(int[][] edges) {
        int[] answer = {0, 0, 0, 0};
        int start = 0;
        int n = 0;
        for(int i=0; i<edges.length; i++){
            n = Math.max(n, Math.max(edges[i][0], edges[i][1]));
        }
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        for(int i=0; i<edges.length; i++){
            graph.get(edges[i][0]).add(edges[i][1]);
        }
        for(int i=1; i<=n; i++){
            if(graph.get(i).size()>=2){
                if(graph.get(i).size()>2){
                    start = i;
                    break;
                }
                else{
                    boolean yes = true;
                    for(int j=0; j<edges.length; j++){
                        if(i==edges[j][1]){
                            yes = false;
                            break;
                        }
                    }
                    if(yes) start = i;
                }
            }
        }
        answer = findGraph(start, n);
        return answer;
    }
    public int[] findGraph(int start, int n){
        Queue<Integer> queue = new LinkedList<>();
        boolean[] check = new boolean[n+1];
        int[] result = new int[4];
        result[0] = start;
        check[start] = true;
        queue.add(start);
        while(!queue.isEmpty()){
            int now = queue.poll();
            for(int next : graph.get(now)){
                if(graph.get(next).size()>=2){
                    result[3]++;
                    continue;
                }
                if(graph.get(next).size()==0){
                    result[2]++;
                    continue;
                }
                if(check[next]){
                    result[1]++;
                    continue;
                }
                check[next] = true;
                queue.add(next);
            }
        }
        return result;
    }
}