링크
https://school.programmers.co.kr/learn/courses/30/lessons/258711
입력 예제
int[][] edges = [[2, 3], [4, 3], [1, 1], [2, 1]]출력 예제
int[] result = [2, 1, 1, 0]풀이
각 그래프의 노드와 에지의 개수는 다음과 같다.
- 도넛
- 정점 = 간선
- 막대
- 정점 = 간선 - 1
- 8자
- 정점 = 간선 + 1
그리고 모든 그래프는 에지로 연결되어 있기 때문에 생성된 노드만 진입 차수가 0이 된다. 또한 그래프 수는 최소 2개 이상이어야 되기 때문에 진출 차수가 2 이상이어야 한다. 따라서 생성된 노드는 다음과 같이 구할 수 있다.
//생성된 노드 찾기
for (int i = 1; i <= N; i++) {
//생성된 노드의 진입 차수는 존재 하지 않고 그래프 수의 합은 2 이상이어야 함
if (inDegree[i] == 0 && outDegree[i] >= 2) {
generatedNode = i;
break;
}
}생성된 노드의 인접 노드부터 탐색을 시작하면 각 그래프에 대해서 탐색할 수 있다. 모든 노드를 탐색하면서 노드의 수와 에지의 수를 구한 뒤 그래프 모양을 판단한다.
private static void bfs(int start) {
Queue<Integer> q = new LinkedList<>();
int nodeCount = 0;
int edgeCount = 0;
q.add(start);
visited[start] = true;
while (!q.isEmpty()) {
Integer cur = q.poll();
nodeCount++;
for (Integer next : adjList.get(cur)) {
edgeCount++;
if (!visited[next]) {
visited[next] = true;
q.add(next);
}
}
}
//노드와 에지의 개수로 그래프 판별
if (edgeCount == nodeCount) {
doughnut++;
} else if (edgeCount == nodeCount - 1) {
stick++;
} else if (edgeCount == nodeCount + 1) {
eight++;
}
}BFS를 이용하지 않고 더 간단하게 해결할 수도 있다. 그래프의 특징을 살펴보면 되는데 생성된 노드의 진출 차수는 총 그래프의 수가 되고, 막대 노드와 8자 그래프 수는 다음과 같은 특징에서 구할 수 있다.
- 막대 노드: 진입 차수가 1이고 진출 차수가 0인 노드(마지막 노드)를 가짐
- 8자 그래프: 진입 & 진출 차수가 2인 노드를 가짐
따라서 다음과 같이 모든 그래프의 수를 구할 수 있다.
for (int i = 1; i <= N; i++) {
if (outDegree[i] >= 2) { //진출 차수가 2 이상이고
if (inDegree[i] == 0) { //진입 차수가 0이면 생성된 노드
generatedNode = i;
} else { //진출 차수가 2인 노드가 존재하면 8자 그래프
eight++;
}
} else if (outDegree[i] == 0 && inDegree[i] >= 1) { //진출 차수가 0이고, 진입 차수가 1개 이상이면 막대 그래프
stick++;
}
}전체 코드
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/*
프로그래머스 / 도넛과 막대 그래프 / Level 2
https://school.programmers.co.kr/learn/courses/30/lessons/258711
*/
class Solution {
private static List<List<Integer>> adjList;
private static boolean[] visited;
private static int doughnut, stick, eight, generatedNode;
//노드와 에지의 개수로 그래프 모양 판단
public int[] solution(int[][] edges) {
int N = 0; //노드의 수
for (int[] edge : edges) {
N = Math.max(N, Math.max(edge[0], edge[1]));
}
adjList = new ArrayList<>();
for (int i = 0; i <= N; i++) {
adjList.add(new ArrayList<>());
}
int[] inDegree = new int[N + 1];
int[] outDegree = new int[N + 1];
visited = new boolean[N + 1];
//인접 리스트 구현 및 진입 & 진출 차수 계산
for (int[] edge : edges) {
adjList.get(edge[0]).add(edge[1]);
inDegree[edge[1]]++;
outDegree[edge[0]]++;
}
//생성된 노드 찾기
for (int i = 1; i <= N; i++) {
//생성된 노드의 진입 차수는 존재 하지 않고 그래프 수의 합은 2 이상이어야 함
if (inDegree[i] == 0 && outDegree[i] >= 2) {
generatedNode = i;
break;
}
}
//생성된 노드부터 탐색 시작
for (Integer next : adjList.get(generatedNode)) {
bfs(next);
}
return new int[]{generatedNode, doughnut, stick, eight};
}
//그래프의 특징으로 그래프 판단
public int[] solution2(int[][] edges) {
int N = 0; //노드의 수
for (int[] edge : edges) {
N = Math.max(N, Math.max(edge[0], edge[1]));
}
int[] inDegree = new int[N + 1];
int[] outDegree = new int[N + 1];
for (int[] edge : edges) {
inDegree[edge[1]]++;
outDegree[edge[0]]++;
}
int generatedNode = 0;
int stick = 0;
int eight = 0;
for (int i = 1; i <= N; i++) {
if (outDegree[i] >= 2) { //진출 차수가 2 이상이고
if (inDegree[i] == 0) { //진입 차수가 0이면 생성된 노드
generatedNode = i;
} else { //진출 차수가 2인 노드가 존재하면 8자 그래프
eight++;
}
} else if (outDegree[i] == 0 && inDegree[i] >= 1) { //진출 차수가 0이고, 진입 차수가 1개 이상이면 막대 그래프
stick++;
}
}
int doughnut = outDegree[generatedNode] - eight - stick;
return new int[]{generatedNode, doughnut, stick, eight};
}
private static void bfs(int start) {
Queue<Integer> q = new LinkedList<>();
int nodeCount = 0;
int edgeCount = 0;
q.add(start);
visited[start] = true;
while (!q.isEmpty()) {
Integer cur = q.poll();
nodeCount++;
for (Integer next : adjList.get(cur)) {
edgeCount++;
if (!visited[next]) {
visited[next] = true;
q.add(next);
}
}
}
//노드와 에지의 개수로 그래프 판별
if (edgeCount == nodeCount) {
doughnut++;
} else if (edgeCount == nodeCount - 1) {
stick++;
} else if (edgeCount == nodeCount + 1) {
eight++;
}
}
}
백엔드