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

문제 주소

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

 

풀이

새로 추가된 정점이 모든 그래프와 연결된다는 것과 그래프의 특성만 알면 쉽게 풀 수 있는 문제였다.

새로 추가된 정점은 들어오는 간선이 없고 나가는 간선이 2개 이상이다.

        if (in[i].size() == 0 && out[i].size() > 1){
            answer[0] = i;
            start_node = out[i];
        }

 

8자 그래프의 중앙에 위치한 정점은 들어오는 간선이 2개, 나가는 간선이 2개이다.

        else if (in[i].size() >= 2 && out[i].size() >= 2){
            // 8자
            answer[3]++;
        }

 

막대 그래프의 마지막에 위치한 정점은 들어오는 간선이 1개 이상, 나가는 간선이 0개이다.

        else if (in[i].size() > 0 && out[i].size() == 0){
            // 막대
            answer[2]++;
        }

 

새로 추가된 정점은 각 그래프와 연결되는 간선이 1개씩 있다.

정점에서 나가는 간선의 개수에서 8자 그래프, 막대 그래프의 개수를 빼주면 도넛 그래프의 개수가 나온다.

    answer[1] = start_node.size() - answer[2] - answer[3];

 

지금 보니 unordered_map<int, vector<int>>가 아니라 <int, int>로 풀어도 되었을 것 같다.

 

코드

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

using namespace std;

vector<int> solution(vector<vector<int>> edges) {
    vector<int> answer(4, 0); // 생성 정점 번호, 도넛, 막대, 8자
    
    unordered_map<int, vector<int>> in;
    unordered_map<int, vector<int>> out;    
    vector<int> start_node;
    int max_node = 0;
    
    for (auto e : edges){        
        in[e[1]].push_back(e[0]);
        out[e[0]].push_back(e[1]);
        
        max_node = max({max_node, e[0], e[1]});
    }
    
    for (int i = 1; i <= max_node; i++){
        if (in[i].size() == 0 && out[i].size() > 1){
            answer[0] = i;
            start_node = out[i];
        }
        else if (in[i].size() >= 2 && out[i].size() >= 2){
            // 8자
            answer[3]++;
        }
        else if (in[i].size() > 0 && out[i].size() == 0){
            // 막대
            answer[2]++;
        }
    }

    answer[1] = start_node.size() - answer[2] - answer[3];
    
    return answer;
}