알고리즘/프로그래머스
도넛과 막대 그래프
베리영young
2024. 7. 6. 15:38
사용 알고리즘: 없...음...
사용 언어: 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는 왜 안 되는 거지? 시간 초과도 아니고 틀리다고 나옴..