프로그래머스 문제 - 도넛과 막대 그래프

프로그래머스 도넛과 막대 그래프 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프들이 있습니다. 이 그래프들은 1개 이상의 정점과, 정점들을 연결하는 단방향 간선으로 이루어져 있습니다.
크기 n의 도넛 모양 그래프는 n개의 정점과 n개의 간선이 있으며, 아무 한 점에서 출발하여 이동한 적 없는 간선을 따라가면 원리 출발했던 정점으로 오게 됨
크기가 n인 막대 모양 그래프는 n개의 정점과 n-1개의 간선이 있으며, 임의의 한 정점에서 출발해 간선을 계속 따라가면 나머지 n-1개의 정점을 한 번씩 방문하게 되는 정점이 단 하나 존재합니다.
크기가 n인 8자 모양 그래프는 2n+1개의 정점과 2n+2개의 간선이 있으며 8자 모양 그래프는 크기가 동일한 2개의 도넛 모양 그래프에서 정점을 하나씩 골라 결합시킨 형태의 그래프입니다.
이 3가지의 그래프가 여러 가지 있으며, 이 그래프와 무관한 정점을 하나 생성한 뒤, 그래프들의 임의의 정점 하나를 연결해주었습니다.
이때, 정점의 번호와 생성된 그래프들의 수를 각각 구해야합니다.

문제 풀이

여러 개의 그래프들을 한 정점에 연결시킨 것이므로, 한 정점을 찾아내야 그래프들의 모양을 알 수 있습니다.
정점은 다른 그래프들과 연결된 정점과는 다르게 정점에서 모든 그래프들의 임의의 정점 하나를 연결한 것이므로, 정점 자신에게 오는 간선은 존재하지 않습니다.
그러므로 그래프의 최소 갯수는 2개이기에, 2개 이상을 잇는 간선을 가지고 자신에게 오는 간선이 존재하지 않는 노드가 정점이 됩니다.

이후 각 그래프들의 임의의 한 점을 알아낼 수 있으니 그래프들의 모양을 찾아주면 됩니다.
그래프 모양에서 간선으로 모양을 알 수 있는 방법이 있습니다.
도넛 모양은 탐색을 시작하여 자기 자신으로 돌아오게 될 경우에 가지는 모양이라는걸 알 수 있으며,
막대 모양은 탐색을 시작한 후 다음으로 연결된 간선이 없는 노드가 나오게 되는 모양이라는걸 알 수 있으며,
8자 모양은 탐색을 시작한 후 2개의 도넛 모양 그래프가 합쳐진 그래프이기 때문에 한 노드가 오는 간선 2개, 가는 간선 2개가 존재하는 모양이라는걸 알 수 있습니다.
탐색을 통해 위의 조건들에 부합하는지 알아보고 알맞는 모양의 수를 배열에 저장해주면 됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

unordered_map<int, vector<int>> node;
vector<int> inNodeCount(1000001, 0);

int dfs(int start)
{
    int nextNum = start;
    while(!node[nextNum].empty())
    {
        if(node[nextNum].size() >= 2)   //간선이 2개 이상일 경우 8자
            return 3;
        
        if(node[nextNum][0] == start)   //자기 자신에게 돌아올 경우 도넛
            return 1;
        else
            nextNum = node[nextNum][0]; //간선이 끝날 경우 막대
    }
    
    return 2;
}

vector<int> solution(vector<vector<int>> edges) {
    vector<int> answer(4, 0);
    //노드 입력
    unordered_map<int, vector<int>>::iterator iter;
    for(vector<int> v : edges)
    {
        iter = node.find(v[0]);
        if(iter == node.end())
            node.emplace(make_pair(v[0], vector<int>()));
        node[v[0]].push_back(v[1]);
        inNodeCount[v[1]]++;
    }
    //정점 탐색
    for(iter = node.begin(); iter != node.end(); iter++)
    {
        if(iter->second.size() >= 2 && inNodeCount[iter->first] == 0)
        {
            answer[0] = iter->first;
        }
    }
    
    for(int curNum : node[answer[0]])
    {
        answer[dfs(curNum)]++;
    }
    
    return answer;
}

출저

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