[코딩테스트] [프로그래머스] 도넛과 막대 그래프

문제

https://school.programmers.co.kr/learn/courses/30/lessons/258711

---

풀이

1. 단방향 그래프는 이중벡터, 각 노드별로 나가는 간선 수 / 들어오는 간선 수는 벡터로 저장한다.

2. 나가는 간선 수가 2개(최소 그래프 개수) 이상이고, 들어오는 간선 수가 하나도 없다면 새로 생성된 노드이다.

3. 새로 생성된 노드에 연결된 노드는, 각 그래프에 포함된 노드이다.
   3-1. 각 그래프에 포함된 노드와 간선 개수를 dfs로 구한다.

4. 노드와 간선 개수를 비교하여 각 그래프 카운트를 증가시킨다.

---

코드

#include <vector>
#include <algorithm>
using namespace std;

void dfs(int current, vector<vector<int>>& adj, vector<int>& visited, int& vertex, int& edge)
{
    visited[current] = true;
    
    vertex++;
    for(int next : adj[current])
    {
        edge++;
        if(!visited[next])
        {
            dfs(next, adj, visited, vertex, edge);
        }
    }
}

vector<int> solution(vector<vector<int>> edges) 
{   
    vector<int> answer(4, 0);
    
    int nodeCount = 0;
    for (auto& info : edges) 
        nodeCount = max(nodeCount, max(info[0], info[1]));
        
    vector<int> inDegree(nodeCount+1);
    vector<int> outDegree(nodeCount+1); 
    vector<vector<int>> adj(nodeCount+1);
    
    for (auto& info : edges) 
    {
        int from = info[0];
        int to   = info[1];
        
        adj[from].push_back(to);
        
        outDegree[from]++;
        inDegree[to]++;
    }
    
    int totalGraphs = 0;

    for (int i = 1; i <= nodeCount; i++) 
    {
        if (inDegree[i] == 0 && outDegree[i] >= 2) 
        {
            answer[0] = i;
            totalGraphs = outDegree[i];
            break;
        }
    }

    vector<int> visited(nodeCount+1, false);
    for (int current : adj[answer[0]]) 
    {
        int vertex =0;
        int edge =0;
        
        dfs(current, adj, visited, vertex, edge);
        
        if (vertex == edge) 
            answer[1]++; 
        else if (vertex - 1 == edge) 
            answer[2]++; 
        else
            answer[3]++;
    }

    return answer;
}