문제 소개
2024 카카오 인턴십 기출 문제를 풀었다. 막대 그래프, 8자 그래프, 도넛 그래프들이 주어지고, 그래프 모두와 연결되어 있는 하나의 정점이 있다. 그 정점을 찾고, 각 종류의 그래프의 개수를 세는 문제이다.
문제 풀이
유일한 정점을 찾는 방법
적어도 두 개 이상의 그래프가 주어진다는 조건에 의해, 그래프 모두와 연결되어 있는 하나의 정점은 반드시 outgoing edge가 두 개 이상 이어야한다. 그리고 그 하나의 정점을 향하는 incoming edge는 존재하지 않는다. 각 노드의 incoming edge와 outgoing edge를 센 뒤 이러한 조건을 만족하는 하나의 정점을 찾는다. 다른 정점들에는 이러한 조건들이 해당하지 않는데, 그 이유는 다음과 같다.
막대 그래프 → 하나의 정점에 outgoing edge가 두 개 이상 존재하지 않음
도넛 그래프 → 모든 정점에 incoming edge가 있음
8자 그래프 → 모든 정점에 incoming edge가 있음그래프의 개수를 계산하는 방법
정점과 연결된 간선을 제외한 모든 간선에 대해 union-find를 수행하여 컴포넌트화하고, 컴포넌트 내의 노드 수와 간선 수을 계산하여, 두 수가 동일할 때는 도넛, 차이가 날 때는 막대와 8자로 각각 분류하여 셀 수 있었다.
오답 노트
그래프가 여러 개 존재하고, 마지막에 생성된 정점이 모든 그래프와 연결될 수 있다는 점을 고려하지 못했다. 그래서, 유일한 그 정점을 찾을 때 그래프로 향하는 outgoing edge의 수를 그래프의 종류의 수인 3개로 제한하고 말았다. 나는 그래프가 세 개까지 생성되었을 때에만 올바르게 작동하는 알고리즘을 작성한 것이다. 이러한 제한을 푸니 통과될 수 있었다.
코드의 깃헙 링크를 남긴다.
https://github.com/Hyungeol94/Software_Competency_Practice/blob/master/2024/20240116%20도넛과%20막대%20그래프/소스.py
