[2024 KAKAO WINTER INTERNSHIP] 도넛과 막대 그래프 [Python]

풀이

도넛, 막대, 8자 그래프의 수와 이를 연결하는 중앙 정점의 번호를 구하는 문제다.

문제에서 그래프 수의 합은 2 이상이라고 주어졌다.

때문에 2개 이상의 단방향 연결을 가지는 정점이 중앙 정점이 될 수 있다.

edges에 대해 다른 정점으로 단방향 연결을 하는지( out ) 연결 되는지( in ) dict을 활용해 기록해 주자.

그래프를 완전 탐색하지 않고, 문제를 해결하는게 중요하다.

각 그래프별 특징을 구해서 선형 탐색으로 풀이해보자.

 

우선 도넛 모양 그래프의 경우 단순히 단방향 연결 여부로만 판단하기에는 그렇다할 특징이 없다.

막대 그래프의 경우 out이 존재하지 않는 정점이 1개 있다.

 

8자 그래프의 경우 out이 2개고, in이 2개인(0이 아닌) 정점이 존재한다.

만약 in이 0이라면 그 정점은 중앙 정점이 된다. 또한, out이 2개를 초과한다면 도넛, 막대, 8자 그래프의 정점에 해당하지 않으므로 중앙 정점이 된다.

 

위의 과정을 통해 중앙정점과 막대, 8자 그래프의 수를 구할 수 있다.

중앙 정점의 out에서 막대와 8자 그래프 수를 빼면 도넛 그래프 수를 쉽게 구할 수 있다.

 

---

소스코드

보기

---

출처

프로그래머스