오랜만에 프로그래머스에 놀러왔더니,
새로운 문제가 업로드가 되어서 너무 기쁜 나머지 하나 풀어보고
해설을 남기게 되었습니다.

카카오 답게, 문제의 퀄리티가 상당한 것을 확인할 수 있었습니다.
덕분에 재밌게 풀었습니다 ^{^}

레벨2 문제 치고는 약간 난이도가 있다는 느낌을 받으셨을거라고 추측되는데요.
그래프 유형의 문제라 좀 더 어렵게 느껴질 수도 있을겁니다.

문제를 간단히 보자면 일자 모양으로 생긴 막대 그래프, 8자 모양으로 순환하는 8자 그래프,
둥그렇게 순환하는 도넛 그래프 이렇게 3개의 유형의 그래프를 임의로 생성하고,
임의의 공간에 임의의 정점 1개를 생성하고 정점으로 부터 출발하여 각 그래프로 이엇다고 했을 때,

[새로 생성한 임의의 정점 번호, 도넛 그래프 갯수, 막대 그래프 갯수, 8자 그래프 갯수]

이렇게 출력 해내는 것이 최종 목표가 됩니다.

그런데, 문제를 읽고 어디서부터 해야하는지 감이 안잡히시는 분들도 계실 것 같습니다.
애초부터 시작 지점을 모르는데, 이 문제를 어떻게 풀어내냐고 생각하시는 분들도 있을 것 같습니다.

하지만, 문제를 잘 살펴보면, 중점을 특정할 수 있게 도와주는 몇 개의 규칙이 존재합니다.
이를 한 번 같이 살펴보겠습니다.

이를 위해서는 각 그래프의 특징과 중점의 특징을 살펴보아야 합니다.

막대 그래프의 특징

• 막대 그래프의 특징은 그래프를 이동하다 보면, 더 이상 갈 곳이 없는 정점이 존재하는 것이 특징입니다.
• 즉, 그래프를 발견하게 되면 쭉 그 경로를 따라 이동하게 되는데 어느 순간 더 이상 탐색할 수 있는 길이 없으면
• 해당 그래프는 막대 그래프라는 특징을 가지고 있습니다.
• 또한, 그래프의 간선은 정점당 하나씩 단방향으로 이어져있다는 사실을 알 수 있습니다.

도넛 그래프의 특징

• 도넛 그래프는 순환그래프라는 특징이 있습니다.
• 순환이 되는 경우는 하나의 경우만 존재한다는 특징이 있습니다.
• 순환이 되는 경우가 오직 하나기에, 같은 정점을 재방문 하게 되었을 때, 그 정점이 시작과 같다면
• 이는 도넛 모양의 그래프라고 할 수 있습니다.
• 또한, 그래프의 간선은 정점당 하나씩 단방향으로 이어져있다는 사실을 알 수 있습니다.

8자 그래프의 특징

• 사실 이 그래프가 가장 문제입니다. 이 것 때문에 고생 길 걷는 분들이 많을거라고 추측됩니다.
• 8자 그래프도 도넛과 마찬가지로 순환하는 그래프이지만, 도넛과는 달리 순환하는 경우가 2개 존재합니다.
• 순환 경로가 2개 존재한다는 의미는 특정 정점에서 2개의 경로로 분기되는 기점을 제공하게 됩니다.
• 막대와, 도넛은 정점 마다 간선이 하나씩 단방향으로 존재하는 그래프였다면, 8자는 중점이 되는 정점에서
• 2가지의 방향으로 가는 간선을 가지고 있게 됩니다.

중심 정점의 특징

• 중심 정점은 그래프와 동 떨어진 위치에 새롭게 만든 정점으로
• 자기 자신으로부터 각각의 그래프를 연결하는 방향으로 간선이 연결되어있습니다.
• 또한, 문제에서 나와있듯이 그래프의 합은 최초 2개부터 시작되므로, 그래프는 자기 자신으로부터 그래프의 진입지점까지
• 적어도 2개의 간선을 내보내게 됩니다.
• 하지만, 이런 특징만으로는 8자 그래프와 일치하는 맥락이 있으므로, 추가적인 조건이 필요하게 되는데요,
• 그것은 바로 중심 정점에는 중심 정점으로 진입하는 간선이 존재하지 않다는 것입니다.
• 다른 그래프들은 전부다 해당 정점을 진입하는 간선 정보가 존재하게 됩니다.
• 즉, 특정 정점에 대해 진입하는 간선이 존재하지 않고, 중점으로 부터 나가는 간선이 2개 이상이라면, 이는 확실히 중심정정이라고 볼 수 있습니다.

정리

이렇게 각각의 그래프에 대한 특징과 중심 정점에 대한 특징을 정리하였습니다.
이를 잘 조합하게 된다면, 문제를 푸는건 순식간입니다.

우선적으로는 중심정점을 찾아야겠죠?
중심정점에 대한 조건을 잘 생각하여, 확실히 찾을 수 있도록 해봅시다.

그리고, 중심 정점에서 나오는 간선의 목적지가, 각 그래프의 시작점이 되게 됩니다.
각각의 그래프를 탐색하여,
시작 정점을 재방문할 경우에는 도넛 모양의 그래프,
더 이상 갈 수 있는 정점이 없는 경우에는 막대 모양의 그래프,
경로가 2개 존재하는 정점이 존재한다면, 8자 모양의 그래프

이렇게 구별해서, 답을 반환해주면 성공적으로 문제를 풀 수 있게됩니다.
또한, 문제에서는 정점의 갯수를 주어지지 않았기에, Map 자료 구조를 사용한다면,
좀 더 편하게 그래프 탐색을 수행할 수 있을 겁니다.

글 읽어주셔서 감사합니다!