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

문제

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

프로그래머스

그래프에 있는 도넛, 막대, 8자 그래프의 개수를 구하는 문제였다.

 

문제 풀이

사실 카카오 코딩테스트를 풀 때 이 문제는 시간이 없어서 덜 푼 문제였었다. 그때도 진입 노드를 저장해 진입 개수가 0인 곳이 root라고 생각은 했었는데, 풀다가 시간이 다 가버렸다..

 

먼저 edges를 돌며 그래프를 만들고, 그래프를 만들면서 in에 각 노드의 진입 개수를 저장했다. 처음에는 진입 노드가 0이기만 하면 root 노드가 되는 줄 알았는데, 테케 2번이 풀리지 않아서 보니 막대 그래프의 맨 끝 노드도 진입 노드가 0이 될 수 있다는 사실을 알게되었다! root node만의 다른 특징이 없을까 하고 생각해 보니, 진입이 0이면서 연결된 노드의 개수가 2개 이상일 경우에는 무조건 root 노드라는 특징이 있었다.

 

처음에는 진입이 0인 노드들을 벡터에 저장하고 차례로 dfs를 돌려 각 그래프의 개수를 계산하고, 그 노드들 중, 전체 그래프 개수와 size가 같은 노드가 root 노드라고 생각하고 풀었는데, 32점이 나왔다;

 

그냥.. 2개 이상일 경우 root 로 만들고 풀이하니 바로 풀렸다.

 

여기까지 생각하는 것이 가장 어려웠고, 도넛/막대/8자 그래프 확인은 문제에서 나와있는 대로 엣지수 노드수를 비교해 쉽게 확인할 수 있었다.

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

using namespace std;

vector<int> G[1000001];
int maxNodeNum;
int edgeNum, nodeNum;

int in[1000001] = {0}; //진입 노드 개수, 0인 곳이 시작 지점
int visit[1000001] = {0};

void printIn(int maxNodeNum){
    for(int i=1;i<=maxNodeNum;i++){
        printf("%d ",in[i]);
    }
    printf("\n\n");
}

void dfs(int n){
    visit[n] = 1;    
    nodeNum++;
    
    for(int i=0;i<G[n].size();i++){
        int nextNode = G[n][i];
        if(visit[nextNode] == 0){
            dfs(nextNode);
        }
        edgeNum++;
    }
}

vector<int> solution(vector<vector<int>> edges) {
    vector<int> answer(4,0);
    int rootNode;
    
    maxNodeNum = edges[0][0];
    
    for(vector<int> edge:edges){
        int a = edge[0];
        int b = edge[1];
        
        G[a].push_back(b);
        in[b]++;        
        int maxNode = max(a,b);
        if(maxNodeNum < maxNode) maxNodeNum = maxNode;
    }
    
    //시작 지점 찾기, 0인게 여러개 있을 수 있음 -> 무조건 막대 시작점이거나, root거나
    //in이 0이고 size가 2 이상인 정점!
    for(int i=1;i<maxNodeNum;i++){
        if(in[i] == 0 && G[i].size() > 1) {
            rootNode = i;
        }
    }
    
    //rootNode와 연결된 node들 dfs 해서 도넛/막대/8자 확인    
    answer[0] = rootNode;

    for(int i=0;i<G[rootNode].size();i++){
        edgeNum = 0;
        nodeNum = 0;    
        int nextNode = G[rootNode][i];
        if(visit[nextNode] == 1) continue;
        dfs(nextNode);
        if(edgeNum == nodeNum){ //도넛
            answer[1]++;
        }
        else if(edgeNum+1 == nodeNum){ //막대
            answer[2]++;
        }
        else{ //8자
            answer[3]++;
        }
    }
    
    return answer;
}