[프로그래머스] 도넛과 막대 그래프 C++ 풀이 및 해설

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

프로그래머스

풀이 방법

생성된 정점은 다음 특징을 갖는다.

1. 생성된 정점으로 진입하는 노드의 개수는 0개이다.
2. 생성된 정점으로부터 진출하는 노드의 개수는 2개이상이다. (이것이 빠지면 막대 그래프의 젤 마지막 노드를 생성된 노드로 오해 가능)

 

이제 위의 특징으로 생성된 노드를 찾았다면

생성된 노드로부터 진출하는 노드는 각각의 그래프의 임의의 정점을 가리킨다.

즉, 생성된 노드의 진출 노드 개수가 그래프의 총 개수가 된다.

이것을 이용해 두개의 그래프 개수를 구하면 총 개수에서 빼면 남은 그래프 종류의 개수를 구할 수 있다.

 

이제 생성된 정점의 진출 노드를 시작으로 그래프 탐색을 시작하자.

그래프를 탐색하며 다음의 특징을 갖는다면 그래프의 종류를 판별할 수 있다.

• 막대 그래프 : 현재 노드로부터 진출 노드의 개수가 0개
• 8자 그래프 : 현재 노드로부터 진출 노드의 개수가 2개
• 도넛 그래프 : 현재 노드로부터 다음 노드가 방문한적 있는 노드이며 처음 탐색을 시작한 노드이다.

 

전체 코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

void searchNode(int start, vector<vector<int>>& input, vector<vector<int>>& output, vector<int>& graphCnt) {
    
    queue<int> q;
    bool visit[1000001];
    fill(visit, &visit[1000001], false);
    
    q.push(start);
    visit[start] = true;
    while(!q.empty()) {
        
        int cur = q.front();
        q.pop();
        
        if (output[cur].size()==0) {
            graphCnt[1]++;
            return;
        } else if (output[cur].size()==2) {
            graphCnt[2]++;
            return;
        }
        
        for(int i=0; i<output[cur].size(); i++) {
            if (visit[output[cur][i]]==false) {
                q.push(output[cur][i]);
                visit[output[cur][i]] = true;
            } else if (visit[output[cur][i]] && output[cur][i]==start) { // 다음 방문지가 이미 방문한곳인데 그게 시작점이라면
                graphCnt[0]++;
                return;
            }
        }
        
    }
    
}

vector<int> solution(vector<vector<int>> edges) {
    vector<int> answer;
    vector<vector<int>> input(1000001);
    vector<vector<int>> output(1000001);
    
    for(int i=0; i<edges.size(); i++) {
        int start = edges[i][0];
        int end = edges[i][1];
        
        input[end].push_back(start);
        output[start].push_back(end);
    }
    
    for(int i=1; i<=edges.size(); i++) {
        if (input[i].size()==0 && output[i].size()>=2) { // 생성한 정점
            answer.push_back(i);
        }
    }
    
    int createNode = answer[0];
    vector<int> graphCnt(3); // 도넛, 막대, 8자
    for(int i=0; i<output[createNode].size(); i++) { // 생성된 정점은 각각의 그래프의 임의 정점을 가리킨다.
        searchNode(output[createNode][i], input, output, graphCnt);
    }
    
    // answer.push_back(output[createNode].size()-graphCnt[1]-graphCnt[2]); <- 도넛 개수 = 총 그래프 개수 - 막대 그래프 개수 - 8자 그래프
    answer.push_back(graphCnt[0]);
    answer.push_back(graphCnt[1]);
    answer.push_back(graphCnt[2]);
    return answer;
}