[프로그래머스] Lv2. 도넛과 막대 그래프

문제

https://school.programmers.co.kr/learn/courses/30/lessons/258711?language=cpp

문제 설명

도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프들이 있습니다. 이 그래프들은 1개 이상의 정점과, 정점들을 연결하는 단방향 간선으로 이루어져 있습니다.

도넛 모양 그래프

 

막대 그래프

8자 그래프

 

위 세가지 그래프가 있는데 이 그래프들과 무관한 정점을 하나 생성하고, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했다. 그 후 각 정점에 서로 다른 번호를 매겼다. 이때 우리는 그래프의 간선 정보가 주어지면, 생성한 정점의 번호와 정점을 생성하기 전 도넛의 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 구해야한다.

 

제한사항

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

 

풀이

 해당 문제는, 처음에 브루트포싱 문제인지, 그래프 탐색 문제인지 고민을 많이 했다. 그런데 이 문제는 규칙을 파악하면 바로 풀리는 문제였다!

 

결과적으로 도넛의 개수를 세는 것이 과제이기 때문에, 무슨 정점이 그래프에 속하는지 알 필요도 없기에, 각 그래프에서 1개씩 꼭 있는 특징을 가진 정점의 개수를 세면 되었다.

 

8자 그래프

8자 도넛의 경우, 교차하는 중간에 있는 노드의 특징이 있다.

잘 보면 다른 노드와 다르게 들어가는 노드와 나가는 노드의 개수가 최소 2개씩 있다!! (여기서 최소 두개씩이라는 점은, 임의로 생성된 노드로 인해서 그런 것이닷!!, 그리고 최소로 참고로 임의로 생성된 정점의 경우 나가는 선이 있기에 엄연히 따지면 나가는 간선 2개, 들어오는 간선이 최소 2개일 것이다!)

 

그렇다는건~~  나가는 간선 2개, 들어오는 간선이 최소 2개인 것이 무조건 8자 도넛에 하나씩 있다는 점!

 

 

막대 그래프

막대 도넛도 특징이 하나 존재한다! 바로 끝나는 점에 대한 특징이 있다.(가장 위의 정점)

가장 위의 정점의 경우, 나가는 간선이 없고, 1개 이상의 들어오는 간선이 존재한다. 심지어 size=1인 가장 작은 도넛에도 이는 적용된다. 왜냐하면 임의로 생성된 간선에서 들어오는 선이 반드시 존재할 것이기 때문이다.

 

도넛 모양 그래프

마지막으로, 도넛 모양 그래프는 직접적으로 찾는 방법보다 더 나은 방법이 있었다. 더욱 획기적인 방법!!

먼저 임의로 생성된 노드를 찾는 조건은 간단하다. 임의로 생성된 정점은, 들어오는 간선은 없으나 나가는 간선이 최소 2개 이상이다. (1개이면, 막대가 될수도!)

 

 이 점을 찾았다면, 이 점을 끊어낸다면 이 선이 연결되어있었던 간선 각각에는 자명하게도 그래프 하나씩 있음을 알 수 있다. 즉 위의 예제에서 4가 임의로 생성된 정점일 것이고, 3개의 간선이 있으므로 총 그래프 수는 3개다.

 

 

즉 결론적으로, 도넛모양 그래프는 (전체 그래프의 개수) - (8자 그래프) - (막대 그래프)가 된다.

 

간단하쥬?

 

최종 코드

#include <iostream>
#include <string>
#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<vector<int>> edges) {
    vector<int> answer = {0,0,0,0};
    
     // 최대 노드 번호를 찾습니다.
    int maxNode = 0;
    for (const auto& entry : edges) {
        maxNode = max(maxNode, max(entry[0], entry[1]));
    }
    
    // 그래프를 빈 벡터로 초기화합니다.
    vector<vector<int>> graph(maxNode + 1); // 나가는 간선
    vector<vector<int>> reversedGraph(maxNode+1); // 들어오는 간선
    
    for (const auto& entry : edges) {
        graph[entry[0]].push_back(entry[1]);
        reversedGraph[entry[1]].push_back(entry[0]);
    }
    
    int total = 0;
    for (int i = 1 ; i < reversedGraph.size(); i++){
        if (reversedGraph[i].size() == 0 && graph[i].size() >= 2){
            answer[0] = i;
            total = graph[i].size();
        }
        else if (reversedGraph[i].size()>=2 && graph[i].size()==2){
            answer[3]++;
        }
        else if (reversedGraph[i].size()>=1 && graph[i].size()==0){
            answer[2]++;
        }

        
    } 
    answer[1] = total-answer[3]-answer[2];
    return answer;
}