[Algorithm] Programmers :: 도넛과 막대그래프

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

프로그래머스

 
int inDegress[1000001] = { 0 };
int outDegrees[1000001] = { 0 };
bool visited[1000001] = { false };
vector<vector<int>> graph(1000001);
int vertexNum = 0;
int edgeNum = 0;
 
void DFS(int node)
{
    if (visited[node]) return;
 
    visited[node] = true;
    ++vertexNum;
    edgeNum += outDegrees[node];
 
    for (int i = 0; i < graph[node].size(); ++i)
    {
        int nextNode = graph[node][i];
        DFS(nextNode);
    }
}
 
vector<int> solution(vector<vector<int>> edges) 
{
    vector<int> answer(4);
 
    int maxVertex = 0;
    int newVertex = 0;
 
    for (int i = 0; i < edges.size(); ++i)
    {
        ++inDegress[edges[i][1]];
        ++outDegrees[edges[i][0]];
 
        graph[edges[i][0]].push_back(edges[i][1]);
 
        maxVertex = max(maxVertex, max(edges[i][0], edges[i][1]));
    }
 
    for (int i = 1; i <= maxVertex; ++i)
    {
        if (inDegress[i] == 0 && outDegrees[i] >= 2)
        {
            answer[0] = newVertex = i;
            break;
        }
    }
 
    for (int i = 0; i < graph[newVertex].size(); ++i)
    {
        int nextNode = graph[newVertex][i];
        vertexNum = 0;
        edgeNum = 0;
 
        DFS(nextNode);
 
        if (vertexNum == edgeNum)
        {
            ++answer[1];
        }
        else if (vertexNum - 1 == edgeNum)
        {
            ++answer[2];
        }
        else if (vertexNum + 1 == edgeNum)
        {
            ++answer[3];
        }
    }
 
    return answer;
}
 
 

 

새 정점을 찾은다음 새정점에 연결된 그래프들의 개수를 구해야하는 문제이다.

즉 새 정점에 연결된 간선의 개수가 총 그래프들의 개수를 의미하며, 해당 간선에 연결된 그래프가 어떤종류인지 구해서 개수를 구해야 한다.

 

일단 새 정점을 찾는게 먼저다. 새정점을 찾으면 간선들은 무조건 새로운 그래프라는게 보장되어지기 때문에 일련의 검사를 통해 그래프종류를 알아내고 카운팅 할 수 있기 때문이다.

 

문제에서 그래프형태 이미지를 보면 생각보다 쉽게 알아챌 수도 있다.

문제설정상, 모든 그래프들을 그린 후에 새 정점을 만든 후 연결했다..라는 설정이기 때문에

새 정점은 들어오는 간선, 즉 inDegree가 무조건 0이다. 

그리고 문제에서 그래프 총개수는 반드시 2이상이라고 되어있기 때문에 새 정점의 outDegree는 무조건 2이상이다.

 

여기까지 하면 일단 새정점은 구했다. 그러면 이제 새정점에 연결된 그래프들의 종류가 어떤것인지 구해야한다.

이부분은 사실 의외로 쉽다. 문제설명에 각 그래프의 특징이 적혀있기 때문이다.

 

1. 도넛그래프 -> 정점개수 == 간선개수

2. 막대그래프 -> 정점개수 - 1 == 간선개수

3. 8자그래프 -> 정점개수 + 1 == 간선개수

 

그러면 우리가 할일은 새정점의 간선에 연결된 각각의 그래프들이 몇개의 정점과 간선으로 이루어져있는지만 구하면 된다. 순환그래프가 존재하기때문에 방문체크는 해주면서하면 최대 정점개수만큼의 탐색으로 완료할 수 있다.

 

그리고 새정점의 각 간선에 연결된 그래프를 탐색할때마다 visited를 false로 초기화 해 줄 필요는 없다.

어차피 각각의 그래프들은 연결되어있지 않기때문에...