프로그래머스 도넛과 막대 그래프 [Lv. 2, 정답률 21%] (C++)

프로그래머스

도넛 모양, 막대 모양, 8자 모양의 그래프가 있고, 모든 그래프로 진입하는 임의의 노드가 있습니다. 해당 문제에서는 임의의 노드의 번호와 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 반환해야 합니다.

 

풀이 방법

우선 새롭게 추가된 임의의 노드가 뭔지 찾아야 합니다.

임의의 노드의 특징을 생각해보면 찾는것은 쉽습니다. 그 특징은 진입 차수가 없고 진출 차수만 있다는 겁니다.

또한 그래프의 수는 항상 2개 이상이기 때문에 진출 차수 - 진입 차수가 2 이상이라면 새롭게 추가된 노드라고 추측해 볼 수 있겠습니다. 

 

vector<vector<int>> in(size);
vector<vector<int>> out(size);

for (auto& edge : edges)
{
    out[edge[0]].push_back(edge[1]);
    in[edge[1]].push_back(edge[0]);

}

// 새롭게 추가된 정점 찾기
for (int i = 1; i < size; i++){
    if (out[i].size() >= in[i].size() + 2){
        NEWNODE = i;           
    }
}

저는 진출 차수와 진입 차수를 사용하지 않고 해당 노드로 진입하는 노드를 저장하는 배열과 해당 노드가 진출하는 다음 노드들을 저장하는 배열을 만들었습니다.

이후 해당 사이즈를 이용하여 새롭게 추가된 노드를 찾았습니다.

여기서 주의 해야할 점은 size() 함수는 size_t 즉, 부호가 없는 정수를 반환하기 때문에 빼기를 하여 비교하면 엉뚱한 수가 나올 수 있습니다.

 

이후에 어떤 그래프인지 체크하는 함수를 만들어서 모든 노드에 대해서 탐색하였습니다.

vector<int> answer(4);
answer[0] = NEWNODE;

vector<bool> visited(size);
for (int i = 1; i < size; i++)
{
    if (i == NEWNODE || 
        in[i].size() + out[i].size() == 0 || visited[i])
        continue;

    answer[CHECK(in, out, visited, i)]++;
}

탐색하려는 노드가 새롭게 추가된 노드이거나 진입, 진출 차수가 없는 노드(존재 하지 않는 노드), 혹은 이미 방문한 노드라면 건너뛰었습니다.

 

 

각 그래프는 고유의 특징이 있습니다. 

1. 도넛 그래프 : 노드의 수와 간선의 수가 같습니다.

2. 막대 그래프 : 노드의 수가 간선의 수보다 1개 더 많습니다.

3. 8자 그래프 : 노드의 수가 간선의 수 보다 1개 더 적습니다.

즉, 해당 그래프의 노드의 수와 간선의 수를 찾고 어떤 그래프인지 반환하면 됩니다.

int CHECK(vector<vector<int>>& in, vector<vector<int>>& out, vector<bool>& visited, int idx)
{
    int edgeCnt = 0;
    
    queue<int> q;
    q.push(idx);
    
    while(!q.empty())
    {
        nodeCnt++;
        int cur = q.front(); q.pop();
        visited[cur] = true;
            
        for (int next : out[cur])
        {
            edgeCnt++;
            if (visited[next] == false)
                q.push(next);
        }
    }
    
    // 막대 끝부분이 들어온 경우 연결된 모든 노드에 체크를 해주어야함
    if (nodeCnt > edgeCnt)
    {
        int IDX = idx;
        q.push(IDX);
        
        while(!q.empty())
        {
            int cur = q.front(); q.pop();
            visited[cur] = true;
            for (int next : in[cur])
                q.push(next);
            
        }
    }
    
    return nodeCnt == edgeCnt ? 1 : nodeCnt > edgeCnt ? 2 : 3;
}

노드의 수와 간선의 수를 찾는 코드의 경우에는 진출 노드 배열을 이용하여 탐색하게 됩니다.

그렇기 때문에 막대 그래프를 탐색할 때 문제가 발생합니다.

 

막대의 중간 ~ 끝 노드부터 탐색을 시작하면 막대의 시작 노드까지는 방문 기록을 못한다는 것 입니다.

이 문제를 해결하기 위해 해당 노드로 진입하는 노드들의 배열을 만들고 인자로 보내주었습니다.

해당 배열을 이용하여 그래프를 거꾸로 탐색하여 모든 노드를 방문했다고 체크 해주어야 합니다.

 

이후 노드 수와 간선의 수가 같다면 1을 반환, 노드 수가 더 크면 2를 반환 그렇지 않으면 3을 반환 하였고

answer[CHECK(in, out, visited, i)]++;

반환된 수를 인덱스로 정답 배열을 업데이트 해주었습니다. 

 

 

정답 코드

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

using namespace std;
int NEWNODE = 0;

int CHECK(vector<vector<int>>& in, vector<vector<int>>& out, vector<bool>& visited, int idx)
{
    int nodeCnt = 0;
    int edgeCnt = 0;
    
    queue<int> q;
    q.push(idx);
    
    while(!q.empty())
    {
        nodeCnt++;
        int cur = q.front(); q.pop();
        visited[cur] = true;
            
        for (int next : out[cur])
        {
            edgeCnt++;
            if (visited[next] == false)
                q.push(next);
        }
    }
    
    // 막대 끝부분이 들어온 경우 연결된 모든 노드에 체크를 해주어야함
    if (nodeCnt > edgeCnt)
    {
        int IDX = idx;
        q.push(IDX);
        
        while(!q.empty())
        {
            int cur = q.front(); q.pop();
            visited[cur] = true;
            for (int next : in[cur])
                q.push(next);
            
        }
    }
    
    return nodeCnt == edgeCnt ? 1 : nodeCnt > edgeCnt ? 2 : 3;
}

vector<int> solution(vector<vector<int>> edges) {
    
    int size = 0;
    for (auto& edge : edges)
        size = max(size, max(edge[0], edge[1]));
    size++;
    
    vector<vector<int>> in(size);
    vector<vector<int>> out(size);
    
    for (auto& edge : edges)
    {
        out[edge[0]].push_back(edge[1]);
        in[edge[1]].push_back(edge[0]);

    }
    
    // 새롭게 추가된 정점 찾기
    for (int i = 1; i < size; i++){
        if (out[i].size() >= in[i].size() + 2){
            NEWNODE = i;           
        }
    }
    
    vector<int> answer(4);
    answer[0] = NEWNODE;
    
    vector<bool> visited(size);
    for (int i = 1; i < size; i++)
    {
        if (i == NEWNODE || 
            in[i].size() + out[i].size() == 0 || visited[i])
            continue;

        answer[CHECK(in, out, visited, i)]++;
    }
    
    return answer;
}