[ 프로그래머스 ] 도넛과 막대 그래프 (C++)

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

 

 edges의 size가 최대 1,000,000이므로 최대 O(n log n)의 시간복잡도를 갖도록 구현해야 한다.

 

[ 풀이 방법 ]

1. 생성한 정점을 찾는 기능

  - 들어오는 edge가 없고 나가는 edge만 존재하는 정점

  - 나가는 edge가 2개 이상이어야 한다.

 

2. 막대 모양 그래프의 개수를 구하는 기능

  - 들어오는 edge만 있거나 나가는 edge만 존재하는 정점

  - 들어오는 edge만 있는 정점의 개수를 센다.

      - 들어오는 edge와 나가는 edge 둘 다 없는 정점도 포함되어야 한다.

 

3. 8자 모양 그래프의 개수를 구하는 기능

  - 들어오는 edge와 나가는 edge가 모두 2개인 정점의 개수를 센다.

 

4. 도넛 모양 그래프의 개수를 구하는 기능

  - 생성한 정점에서 나가는 edge의 개수는 모든 모양 그래프의 개수

  - (생성한 정점에서 나가는 edge - 막대 모양 그래프와 8자 모양 그래프의 개수의 합)으로 도넛 모양 그래프의 개수를 구한다.

 

 먼저, 주어진 edges를 탐색하며 노드 번호별로 들어오는 edge와 나가는 edge의 개수를 세 저장한다(map을 이용).

 이후, 저장된 들어오는 edge와 나가는 edge의 개수를 이용해 생성한 정점을 찾고 생성한 정점과 edge로 연결된 노드들의 들어오는 edge 개수를 한 개 줄인다.

 마지막으로 생성한 정점을 제외한 노드들을 탐색하여 도넛, 막대, 8자 모양 그래프의 개수를 구한다.

 

[ 회고 ]

 DFS를 이용한 그래프 탐색과 cycle detection만 생각하고 나가는 edge만을 이용하는 방식으로 풀이 방법을 생각했기 때문에 들어오는 edge와 나가는 edge를 모두 고려하는 올바른 풀이 방법을 생각해내지 못했다.

 

 그래프 이론에 대한 복습이 필요하다고 느낄 수 있었고, 그래프 관련 문제의 풀이 방법에 대한 시야가 넓어진 문제였다.

 

[ 정답 코드 ]

#include <string>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

int createdNode;
vector<int> nodes;
map<int, int> inCnt;
map<int, int> outCnt;

int total = 0;
int eight = 0;
int donut = 0;
int rod = 0;

vector<int> solution(vector<vector<int>> edges) {
    
    for(int i = 0; i < edges.size(); i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        
        nodes.push_back(u);
        nodes.push_back(v);
        
        outCnt[u]++;
        inCnt[v]++;
    }
    
    sort(nodes.begin(), nodes.end());
    nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
    
    for(int i = 0; i < nodes.size(); i++) {
        int nodeNum = nodes[i];
        if(inCnt[nodeNum] == 0 && outCnt[nodeNum] >= 2) {
            createdNode = nodeNum;
            break;
        }
    }
    
    for(int i = 0; i < edges.size(); i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        
        if(u == createdNode) {
            inCnt[v]--;
            total++;
        }
    }
    
    for(int i = 0; i < nodes.size(); i++) {
        
        int nodeNum = nodes[i];
        if(nodeNum == createdNode) continue;
            
        if(inCnt[nodeNum] >= 0 && outCnt[nodeNum] == 0) {
            rod++;
        } else if(inCnt[nodeNum] >= 2 && outCnt[nodeNum] >= 2) {
            eight++;
        }
    }
    donut = total - (rod + eight);
    
    vector<int> answer = {createdNode, donut, rod, eight};
    
    return answer;
}