도넛과 막대 그래프 (그래프 탐색) [Lv.2]

프로그래머스

 

3개의 모양(도넛, 막대, 8) 중 하나를 가지는 그래프가 2개 이상 있는 상황에서

그래프에 포함되지 않으면서 모든 그래프에 연결하는 새 노드를 추가할 때

추가된 노드의 번호와 그래프 모양별 개수를 찾는 문제입니다.

 

풀이법

우선 추가된 노드를 찾아야합니다. 추가된 노드의 조건은

2개 이상의 진출 차수 + 0개의 진입차수 이기에 어렵지 않게 찾을 수 있을 것 입니다.

 

추가된 노드는 모든 그래프에 연결되어 있습니다.

이 노드와 연결된 다른 노드에서 부터 그래프 순회를 시작하면 되겠습니다.

 

그래프 모양을 체크하는 방법은 아래와 같습니다.

도넛 = 노드 수 == 간선 수
팔 = 노드 수 = 간선 수 - 1
바 = 노드 수 = 간선 수 + 1

 

그래프를 순회하여 노드와 간선의 수를 찾고

도넛인지 팔인지 바 모양인지 확인하면 아주 쉽게 풀 수 있을 것 같습니다.

 

 

정답 코드

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

using namespace std;

static int _newNode, _donutCount, _barCount, _eightCount;
static vector<vector<int>> v;
static vector<pair<int, int>> degree; // in, out
static vector<bool> visited;

void BFS(int start);

vector<int> solution(vector<vector<int>> edges)
{
    int size = 0;
    for (auto edge : edges)
        for (auto i : edge)
            size = max(size, i);

    v.resize(size + 1);
    degree.resize(size + 1);
    visited.resize(size + 1);

    for (auto edge : edges)
    {
        v[edge[0]].push_back(edge[1]);
        degree[edge[0]].second++;
        degree[edge[1]].first++;
    }

    for (int i = 0; i < degree.size(); i++)
    {
        if (degree[i].first == 0 && degree[i].second >= 2)
            _newNode = i;
    }

    for (int i : v[_newNode])
        BFS(i);


    return { _newNode, _donutCount, _barCount, _eightCount };
}

 

 

 

void BFS(int start)
{
    int edgeCount = 0;
    int nodeCount = 1;

    queue<int> q;
    q.push(start);

    while (q.size())
    {
        int cur = q.front();
        q.pop();

        visited[cur] = true;
        
        for (int next : v[cur])
        {
            edgeCount++;

            if (visited[next] == false) {
                nodeCount++;
                q.push(next);
            }
        }
    }

    if (edgeCount == nodeCount - 1) {
            //  cout << "########## BAR COUNT UP ! ! ! ##########" << "\n"  ;
            _barCount++;
    }

    else if (edgeCount == nodeCount + 1) {

            //cout << "########## EIGHT COUNT UP ! ! ! ##########" << "\n"  ;
            _eightCount++;

    }
    else if (edgeCount == nodeCount)
    {
            //cout << "########## DONUT COUNT UP ! ! ! ##########" << "\n"  ;
            _donutCount++;
    }
    //cout << "\n";
}