[Programmers] 도넛과 막대 그래프

프로그래머스

 

1. 문제 설명

 

2. 구현 아이디어 1 - 정답입니다!

처음에는 Union-Find 알고리즘을 사용해서 사이클이나 parent를 구하여 푸는 방법을 생각했다.

하지만 완전 탐색 없이 생성한 정점을 구하는 방법이 떠오르지 않아 다른 사람의 풀이를 참고하여 문제를 풀었다 ㅠ^ㅠ

 

Key Point: 들어오는 간선과 나가는 간선의 수를 활용하자

 

의외로 쉬운 방법으로 문제를 풀 수 있던 것이였다 ...!! (오히려 그래프 알고리즘을 사용하면 시간 복잡도가 커진다)

 

생성한 정점, 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수의 특징을 찾으면 아래와 같다.

 

• 생성한 정점: 들어오는 간선 0개, 나가는 간선 2개 이상
• 막대 모양 그래프의 수: 들어오는 간선 1개, 나가는 간선 0개인 노드의 개수
• 8자 모양 그래프의 수: 들어오는 간선 2개, 나가는 간선 2개인 노드의 개수
• 도넛 모양 그래프의 수:  (생성한 정점에서 나가는 간선의 수) - (막대 모양 그래프의 수) - (8자 모양 그래프의 수)
  • 생성한 정점에서 나가는 간선의 수는 도넛, 막대, 8자 모양 그래프의 수의 합과 같다

 

근데 위에서 말하는 그래프의 수는 생성한 정점으로부터 들어오는 간선을 고려하지 않았기 때문에 막대 모양 그래프의 수와 8자 모양 그래프의 수의 조건을 각각 들어오는 간선 1개 이상, 들어오는 간선 2개 이상으로 변경해야 한다.

 

위 아이디어를 사용한 구체적인 구현 로직은 아래와 같다.

1. 들어오는 간선과 나가는 간선의 개수를 저장하는 벡터를 만든다
2. 입력으로 들어오는 edges를 순회하며 노드별 들어오는 간선과 나가는 간선의 개수를 계산한다
3. 들어오는 간선, 나가는 간선의 수 특징을 사용하여 생성한 정점, 막대 모양 그래프의 수, 8자 모양 그래프의 수, 도넛 모양 그래프의 수를 구한다.

 

#include <vector>

#define NODE_MAX 1'000'001

using namespace std;

vector<int> solution(vector<vector<int>> edges) {
    // {생성한 정점의 번호, 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수}
    vector<int> answer = {0, 0, 0, 0};
    
    // 들어오는 간선의 수
    vector<int> in = vector<int>(NODE_MAX, 0);
    // 나가는 간선의 수
    vector<int> out = vector<int>(NODE_MAX, 0);
    
    for (auto edge : edges) {
        // [a, b]일 때, a에서 나가는 간선이 1개 증가하고 b로 들어오는 간선이 1개 증가
        in[edge[1]]++;
        out[edge[0]]++;
    }
    
    for(int i=1; i< NODE_MAX; i++) {
        // 생성한 정점
        if (in[i] == 0 && out[i] >= 2) answer[0] = i;
        
        // 막대
        else if (in[i] >= 1 && out[i] == 0) answer[2]++;
        
        // 8자
        else if (in[i] >= 2 && out[i] == 2) answer[3]++;
    }
    
    // 도넛
    answer[1] = out[answer[0]] - answer[2] - answer[3];
    
    
    return answer;
}

---

Reference

• https://velog.io/@mino0121/ProgrammersPython-%EB%8F%84%EB%84%9B%EA%B3%BC-%EB%A7%89%EB%8C%80%EA%B7%B8%EB%9E%98%ED%94%84