도넛과 막대 그래프
📚 문제 설명
자세한 문제 설명은 위의 링크를 들어가서 보도록 하고 간략하게만 설명하겠다.
여러개의 노드와 단방향 간선으로 이루어진 그래프들이 있다고 한다.
그리고 각각의 그래프는 막대 그래프, 8 모양 그래프, 도넛 모양 그래프가 갯수는 랜덤으로 있다고 한다.
그리고 그래프와 상관이 없는 위치의 정점에서 모든 그래프를 연결하고 모든 간선들을 edges 로 줄 때,
[ 정점, 도넛 그래프의 수, 막대 그래프의 수, 8 그래프의 수 ] 를 구하여라.
단, 모든 그래프 수의 합은 2 이상이다.
👨🏻💻 풀이 과정
이 문제의 핵심은 노드에서 나가는 간선(Out)과 들어오는 간선(In)의 수이다.
결국 정점은 다신에게 들어오는 간선은 없고 나가는 간선 Out만 존재하고 Out 의 갯수가 바로 전체 그래프의 갯수이다.
그럼 각 그래프의 특징을 알아보면, 8 모양의 그래프에는 8 모양의 가운데 부분에서 반드시 Out 의 갯수가 2개가 되는 노드가 존재해야 하고,
막대 그래프의 경우 Out 이 0인 노드가 반드시 1개 존재해야 한다.
그리고 도넛 모양의 그래프의 갯수는
전체 그래프의 수 - 8모양 그래프의 수 - 막대 그래프의 수
로 계산을 해줄 수 있다.
그럼 이제 정점 어떤 노드인지 구하면 끝이다.
문제에서 주어진 조건인 그래프 수의 합은 2 이상이어야 한다는 조건 때문에 정점의 Out 은 반드시 2 이상이어야 하고, In 은 없어야 한다.
그럼 전체 로직을 살펴 보자.
- 모든 노드를 객체에
[ 들어오는 간선의 수 (IN), 나가는 간선의 수 (Out) ]로 저장해준다. Out=== 0 이면 막대 그래프 갯수 증가.Out=== 2 일 때,IN> 0 이면 8모양 그래프 갯수 증가.- 아니라면 정점.
Out> 2 라면 정점.
전체 풀이
function solution(edges) {
let nodes = {};
// [In, Out] 으로 저장
for (const edge of edges) {
const [a, b] = edge;
nodes[a] = nodes[a] ? [nodes[a][0], nodes[a][1] + 1] : [0, 1];
nodes[b] = nodes[b] ? [nodes[b][0] + 1, nodes[b][1]] : [1, 0];
}
// [ 정점, 도넛, 막대, 8 ]
let answer = new Array(4).fill(0);
// 각각의 노드를 돌며 확인.
for (const nodesKey in nodes) {
const [In, Out] = nodes[nodesKey];
if (Out === 0) {
answer[2]++;
} else if (Out === 2) {
if (In > 0) {
answer[3]++;
} else {
answer[0] = parseInt(nodesKey);
}
}else if (Out > 2) {
answer[0] = parseInt(nodesKey);
}
}
// 도넛 모양 그래프의 수 계산
answer[1] = nodes[answer[0]][1] - (answer[2] + answer[3]);
return answer;
}
🧐 후기
문제를 똑바로 읽지 않아서 정점의 IN 이 0이 라는 사실과, 그래프의 합이 반드시 2 이상이라는 것을 몰라서 고민을 하는데 너무 힘들었던 문제였다.
결국 고민을 하다가 다른 사람의 풀이를 보고 나서 그런 조건이 있다는 것을 확인한 이후에는 생각보다 쉽게 풀 수 있었다.
