[2024 카카오 겨울 인턴십 코딩테스트] 도넛과 막대 그래프 (C++)

✍ 문제

문제는 프로그래머스에서 확인해주세요!
프로그래머스 2024 KAKAO WINTER INTERNSHIP 도넛과 막대 그래프

---

✍ 제한 사항

1 ≤ edges의 길이 ≤ 1,000,000
edges의 원소는 [a,b] 형태이며, a번 정점에서 b번 정점으로 향하는 간선이 있다는 것을 나타냅니다.
1 ≤ a, b ≤ 1,000,000

문제의 조건에 맞는 그래프가 주어집니다.
도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다.

---

✅ 코드

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

vector<int> solution(vector<vector<int>> edges) {
    vector<int> answer;
    map<int, vector<int>> inout;
    int edgeNum = edges.size();     //간선의 개수
    int vertex;                     //생성된 정점
    int graphNum;                   //전체 그래프의 개수
    
    for (int i = 0; i < edgeNum; i++) {
        //edges[i][0] -> edges[i][1] 간선 존재
        int from = edges[i][0];
        int to = edges[i][1];
        if (inout.find(from) != inout.end()) inout[from][1]++;
        else inout[from] = {0, 1};
        if (inout.find(to) != inout.end()) inout[to][0]++;
        else inout[to] = {1, 0};
    }
    
    for (auto v: inout) {
        if(v.second[0] == 0 && v.second[1] >=2) {
            vertex = v.first;
            graphNum = v.second[1];
            break;
        }
    }
    
    for (int i = 0; i < edgeNum; i++) {
        if (edges[i][0] == vertex) inout[edges[i][1]][0]--;
    }
    
    int donut = 0;
    int stick = 0;
    int eight = 0;
    
    for (auto v: inout) {
        if (v.second[0] == 0 && v.first != vertex) stick++;
        if (v.second[0] == 2 && v.second[1] == 2) eight++; 
    }
    donut = graphNum - stick - eight;
    
    answer = {vertex, donut, stick, eight};
    
    return answer;
}

✅ 코드풀이

이 문제에서 가장 핵심이 되는 아이디어는 각 정점별 나가는 들어오는 간선의 개수, 나가는 간선의 개수로 그래프 종류를 파악하는 것이다.

결과적으로 구해야 하는 속성은 총 4가지이다.

• 그래프와 무관하게 생성한 정점의 번호
• 도넛 그래프 개수
• 막대 그래프 개수
• 8자 모양 그래프 개수

각 속성을 구별할 수 있는 특징을 정리하면 아래와 같다.

• 그래프와 무관하게 생성한 정점의 번호
  • 들어오는 간선의 개수 = 0
  • 나가는 간선의 개수 >= 2 (문제 조건: 총 그래프의 수는 2개 이상)

아래 그래프의 특성은 생성한 정점으로 인해 생긴 간선은 제외하고 정의한 것이다.

• 도넛 그래프 개수
  • 모든 정점이 들어오는 간선의 개수 = 1 and 나가는 간선의 개수 = 1
• 막대 그래프 개수
  • 들어오는 간선의 개수 = 0 or 나가는 간선의 개수 = 0 인 정점 존재
  • 나머지 정점은 들어오는 간선의 개수 = 1 and 나가는 간선의 개수 = 1
• 8자 모양 그래프 개수
  • 들어오는 간선의 개수 = 2 or 나가는 간선의 개수 = 2 인 정점 한 개 존재
  • 나머지 정점은 들어오는 간선의 개수 = 1 and 나가는 간선의 개수 = 1

각 정점 별로 들어오고 나가는 간선의 개수를 저장하기 위해 map 자료 구조를 사용하였다.

key: 정점(노드) 번호 int
value: 들어가는 간선 개수[0], 나가는 간선 개수[1] 를 원소로 가지는 vector

map<int, vector<int>> inout;

/*
inout[3][0]  = 2 
3번 정점으로 들어오는 간선의 개수 = 2
inout[3][1] = 1
3번 정점에서 나가는 간선의 개수 1
*/

위와 같이 정의한 간선 개수 정보를 담은 inout map과 4가지 속성의 특성을 고려했을 때 다음과 같은 순서대로 각 속성의 값을 구할 수 있다.

1. edges 벡터를 순회하며 각 정점별 in, out 간선의 개수를 inout map에 저장한다.
2. inout map을 순회하며 생성한 정점의 번호(속성1)를 찾는다.
   inout[i][0] == 0 && inout[i][1] >= 2 를 만족하는 i가 생성한 정점의 번호가 된다.
   이 때 이 정점에서 나가는 간선의 개수가 전체 그래프 개수의 합이 된다.
3. 생성한 정점에서 시작된 간선을 삭제한다.
   ➡️ edges 벡터를 순회하며 해당 정점에서 가리키는 정점의 inout[][0] 값을 1 감소시킨다.
4. 다시 inout map을 순회하며 막대 그래프의 개수(속성3)과 8자 모양 그래프의 개수(속성4)를 구한다.
   ➡️ 들어오는 간선의 개수 = 0 인 정점의 개수가 막대 그래프의 개수가 된다.
   ➡️ 들어오는 간선의 개수 = 2 and 나가는 간선의 개수 = 2 인 정점의 개수가 8자 모양 그래프의 개수가 된다.
5. 2번에서 구한 전체 그래프의 개수에서 막대, 8자 모양 그래프의 개수를 빼 도넛 모양 그래프(속성2)의 개수를 구한다.

---

❗ 문제를 풀 때 처음에는 개별 간선 자체를 이용하여 문제를 접근하려고 했다. 그러다보니 풀이 설계가 어려워지고, 구현도 너무 복잡해져서 갈피를 잃어버렸다. 결국 카카오테크 블로그에서 올려준 공식 해설을 보고 나서야 풀 수 있었다. 엄청 복잡한 문제인 줄 알았는데 간선 개수라는 포인트만 잡으면 이후는 엄청 간단했던 문제라서 혼자서 해결하지 못한 것이 너무 아쉬웠다...😵‍💫 또 3개의 개수를 각각 구하지 않고도 전체에서 나머지 2개를 뺌으로서 마지막 남은 하나의 개수도 구할 수 있다는 생각도 잘 떠올리지 못했다!

문제를 더 많이 풀어보면서 생각의 유연성을 길러야겠다!! 💪

[참고자료]

카카오테크 블로그 공식 해설