도넛과 막대 그래프

사용 알고리즘: 없...음...

사용 언어: java

 

import java.io.*;
import java.util.*;
/*
생성된 정점의 조건
1. 들어오는 애가 0
2. 나가는 애는 2이상

들어옴:0 + 나감:1 이면 막대 모양 그래프의 시작

// 생성된 정점에서 나가는 개수만큼 그래프가 있는 건데, 어떤 모양인지 확인~

들어옴:1 + 나감:1 이면 도넛 모양 그래프 or 막대 모양 그래프 중간

들어옴:2이상 + 나감:2이상 이면 8자 모양 그래프
*/
class Solution {
    static ArrayList<Integer>[] path;
    static int[][] ioCnt; //[?][0]: 들어오는 개수, [?][1]: 나가는 개수
    
    public int[] solution(int[][] edges) {
        
        //메인
        int len = 0;
        for(int i=0; i<edges.length; i++) { //가장 끝 node 찾기 = 길이 
            for(int j=0; j<2; j++) len = Math.max(len, edges[i][j]);
        }
        
        ioCnt = new int[len + 1][2];
        
        path = new ArrayList[len + 1];
        for(int i=0; i<len + 1; i++) {
            path[i] = new ArrayList<>();
        }
        
        for(int i=0; i<edges.length; i++) {
            int start = edges[i][0];
            int end = edges[i][1];
            
            path[start].add(end);
            ioCnt[end][0]++;
            ioCnt[start][1]++;
        }
        // for(int i=1; i<len+1; i++) {
        //     System.out.print(ioCnt[i][0]+" "+ioCnt[i][1]);
        //     System.out.println();
        // }
        
        int[] answer = new int[4]; //정점 번호, 도넛, 막대, 8자
        
        //허헣
        for(int i=1; i<len+1; i++) {
            if(ioCnt[i][0] == 0 && ioCnt[i][1] > 1) {
                answer[0] = i; //생성된 정점 구하기
            }
            
            if(ioCnt[i][0] >= 1 && ioCnt[i][1] == 0) answer[2]++; //막대 그래프
            if(ioCnt[i][0] >= 2 && ioCnt[i][1] >= 2) answer[3]++; //8자 그래프
        }
        answer[1] = ioCnt[answer[0]][1] - answer[2] - answer[3];
        
        
        //생성된 정점에서 나가는 개수만큼, 그래프 모양 구하기~
//         for(int i=0; i<ioCnt[answer[0]][1]; i++) {
//             int start = path[answer[0]].get(i);
            
//             if(ioCnt[start][1] == 0 || ioCnt[start][0] ==1 && ioCnt[start][1] == 1) { //막대임
//                 answer[2]++;
//             }
//             else {
//                 //어쩔 수 없이 돌면서, 간선 개수와 정점 개수 세기
//                 boolean[] visit = new boolean[len+1];
//                 visit[start] = true;
                
//                 if(kinda(start, visit) == 1) {
//                     //도넛 (간선==정점)
//                     answer[1]++;
//                 }
//                 else if(kinda(start, visit) == 2) {
//                     //막대 (간선 < 정점)
//                     answer[2]++;
//                 }
//                 else {
//                     //8자 (간선 > 정점)
//                     answer[3]++;
//                 }
//             }
//         }
        
        return answer;
        //메인--
    }
    
//     private static int kinda(int start, boolean[] visit) {
//         int nodeCnt = 0;
//         int edgeCnt = 0;
        
//         Queue<Integer> q = new ArrayDeque<>();
//         q.add(start);
        
//         while(!q.isEmpty()) {
//             int cur = q.poll();
//             nodeCnt++;
//             edgeCnt += ioCnt[cur][0] + ioCnt[cur][1]; // 나가는 것만 더하면, 8자는 찾을 수 없음
            
//             if(ioCnt[cur][1] == 0) return 2; //끝에서 나가는 간선이 없으면 막대 그패르
//             if((ioCnt[cur][0]==2 || ioCnt[cur][0]==3)&&ioCnt[cur][1]==2 ) return 3;
            
//             for(int nxt: path[cur]) {
//                 if(!visit[nxt]) {
//                     visit[nxt] = true;
//                     q.add(nxt);
//                 }
//             }
//         }
        
        
//         if(nodeCnt == (edgeCnt-1)/2 ) return 1;
//         // else if(nodeCnt < (edgeCnt-1)/2) return 3;
//         else return 3;
//     }
    
}

 

bfs로 풀다가 답이 안 나와서 슬퍼하다가 

블로그 글 참고해서 풂..

커허허허

 

근데 이 bfs는 왜 안 되는 거지? 시간 초과도 아니고 틀리다고 나옴..