[2024 KAKAO WINTER INTERNSHIP] 도넛과 막대 그래프 (C++)

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

프로그래머스

풀이

위 문제를 풀기 위해서는 다음과 같은 과정을 거쳐야 한다.

 

1. 생성된 정점이 무엇인지 찾기

2. 생성된 정점과 정점으로부터 이어진 간선을 그래프에서 제외하기

3. 그래프의 모양(도넛, 막대, 8자)을 파악하고 개수 구하기

 

먼저 1번부터 진행해보자.

생성된 정점에는 한 가지 특징이 있는데, 나가는 간선은 그래프의 개수만큼 존재하지만 들어오는 간선의 개수는 존재하지 않는 것이다.

즉, 각 정점들의 나가는 간선의 개수와 들어오는 간선의 개수를 구하면 생성된 정점을 쉽게 구할 수 있다.

그런데 문제가 하나 존재하는데, SIZE가 2 이상인 막대 모양 그래프의 시작점의 경우 생성된 정점과 마찬가지로 나가는 간선은 존재하고, 들어오는 간선은 존재하지 않다는 것이다.

 

그런데 문제의 제한사항을 자세히 읽어보면 다음과 같은 사실을 알 수 있다.

"도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2 이상입니다."

이는 생성된 정점에서 나가는 간선이 2개 이상임을 의미하고, 막대 모양 그래프의 시작점의 경우 나가는 간선은 1개이기 때문에 "나가는 간선의 개수가 2이상이면서 들어오는 간선의 개수가 0인 점"이 생성된 정점이다.

 

2번의 경우 간단히 vistied 배열을 정의하여 해결할 수 있고, 문제는 3번이다.

먼저 막대 모양 그래프는 앞서 말했듯 쉽게 파악할 수 있다. 정점의 들어오는 간선이 존재하지 않는다면 이는 막대 모양 그래프의 정점(구체적으로는 시작점)임을 알 수 있다.

 

다음으로 8자 모양 그래프는 8자의 중앙 부분을 조사한다면 쉽게 파악할 수 있다.

 

도넛 모양 그래프 2개를 연결한 모양인 8자 모양 그래프는 중앙의 정점에서 두 그래프를 연결한 듯한 모양을 하고 있다.

그리고 중앙의 정점은 들어오는 나가는 간선의 개수가 2개, 들어오는 간선의 개수가 2개이다.

이를 통해 8자 모양 그래프의 개수를 구할 수 있다.

 

마지막으로 도넛 모양 그래프은 간접적으로 쉽게 구할 수 있다.

전체 그래프의 개수는 생성된 정점에서 나가는 간선의 개수와 같으므로 쉽게 구할 수 있고

도넛 모양 그래프의 개수는 (전체 그래프의 개수 - 막대 모양 그래프의 개수 - 8자 모양 그래프의 개수)이다.

이를 통해 생성된 정점의 번호, 각 모양 그래프의 수를 모두 구할 수 있다.

코드

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

// 나가는 간선의 개수, 들어오는 간선의 개수 저장
int nodeInfo[1000001][2];
// 그래프 정보 저장
vector<int> graph[1000001];
// 방문 처리
bool visited[1000001];


vector<int> solution(vector<vector<int>> edges) {
    vector<int> answer;
    
    vector<int> nodes;
    for (int i = 0; i < edges.size(); i++){
        graph[edges[i][0]].push_back(edges[i][1]);
        nodes.push_back(edges[i][0]);
        nodes.push_back(edges[i][1]);
        // 위상 정렬(나가는 간선의 개수, 들어오는 간선의 개수 count)
        nodeInfo[edges[i][0]][0]++;
        nodeInfo[edges[i][1]][1]++;
    }
    unique(nodes.begin(), nodes.end());
    sort(nodes.begin(), nodes.end());
    
    // 나가는 간선의 개수가 2 이상이면서 들어오는 간선의 개수가 0이라면 생성된 정점임
    int createdNode, numGraphs;
    for (int i = 0; i < nodes.size(); i++){
        if (nodeInfo[nodes[i]][0] >= 2 && nodeInfo[nodes[i]][1] == 0){
            createdNode = nodes[i];
            numGraphs = nodeInfo[nodes[i]][0];
            break;
        }
    }
    visited[createdNode] = true;
    
    int numStick = 0, numEight = 0;
    
    // BFS로 탐색하며 각 그래프의 모양을 판단
    for (int i = 0; i < nodes.size(); i++){
        int cur = nodes[i];
        bool isStick = false;
        bool isEight = false;
        queue<int> q;
        if (!visited[cur]){
            q.push(cur);
            
            while (!q.empty()){
                int node = q.front();
                visited[node] = true;
                q.pop();
                // 막대인지 판단
                if (graph[node].size() == 0){
                    isStick = true;
                }
                // 8자인지 판단
                else if (graph[node].size() == 2){
                    isEight = true;
                }
                
                for (int j = 0; j < graph[node].size(); j++){
                    int nextNode = graph[node][j];
                    if (!visited[nextNode]){
                        q.push(nextNode);
                    }
                }
            }
            if (isStick){
                numStick++;
            }
            else if (isEight){
                numEight++;
            }
        }
    }
    
    answer = {createdNode, numGraphs-numStick-numEight, numStick, numEight};
    
    
    return answer;
}