[C++] 프로그래머스(Lv.2) 도넛과 막대 그래프

 

난이도 :  Lv2 (상)

알고리즘 유형 : BFS, DFS

풀이 방법 : BFS를 이용한 사이클 계산 

 

문제 링크

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

프로그래머스

 

문제 예시

 

 

크기가 n인 도넛 모양 그래프는 n개의 정점과 n개의 간선이 있습니다. 

도넛 모양 그래프의 아무 한 정점에서 출발해 이용한 적 없는 간선을 계속 따라가면 

나머지 n-1개의 정점들을 한 번씩 방문한 뒤 원래 출발했던 정점으로 돌아오게 됩니다. 

도넛 모양 그래프의 형태는 다음과 같습니다.

 

 

크기가 n인 막대 모양 그래프는 n개의 정점과 n-1개의 간선이 있습니다. 

막대 모양 그래프는 임의의 한 정점에서 출발해 간선을 계속 따라가면 

나머지 n-1개의 정점을 한 번씩 방문하게 되는 정점이 단 하나 존재합니다. 

막대 모양 그래프의 형태는 다음과 같습니다.

 

 

 

 

크기가 n인 8자 모양 그래프는 2n+1개의 정점과 2n+2개의 간선이 있습니다. 

8자 모양 그래프는 크기가 동일한 2개의 도넛 모양 그래프에서

정점을 하나씩 골라 결합시킨 형태의 그래프입니다. 

8자 모양 그래프의 형태는 다음과 같습니다.

 

이 그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 

8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했습니다.

그 후 각 정점에 서로 다른 번호를 매겼습니다.
이때 당신은 그래프의 간선 정보가 주어지면 생성한 정점의 번호와 정점을 생성하기 전

도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 구해야 합니다.

 

 

첫 번째 핵심은 임의의 새로운 정점을 구하는 것입니다.

새로운 정점은 말 그대로 새로 생긴 정점이기 때문에 그 정점에 오는 간선이 없습니다.

그리고 막대, 도넛, 8자 모든 그래프에 나가는 간선들이 연결되어있기 때문에

모든 정점을 탐색해 비교적 쉽게 구할 수 있습니다. 

 

두 번째 핵심은 사이클의 유무와 간선입니다.

사이클이 있을 경우      　　사이클이 없을 경우

도넛 OR 8자　　　　 　　막대

 

 

사이클을 찾을 수 있는 그래프 탐색을 수행하여 사이클을 구하고,

만약 사이클이 없다면 막대 그래프입니다.

 

만약 사이클을 찾았다면 도넛 또는 8자 일텐데, 거리를 비교합니다. 

 

도넛 : n개의 정점과 n개의 간선

8자 : 2n+1개의 정점과 2n+2

 

만약 이  정점을 이동한 횟수와 이동한 거리가 같다면,

n개의 간선을 이동했기 때문에 도넛이며, 아니라면 8자로 수렴합니다. 

 

이렇게 새로운 정점과 도넛, 막대, 8자를 구할 수 있습니다.

아래는 코드입니다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

// 생성한 정점의 번호
// 도넛 모양 그래프의 수
// 막대 모양 그래프의 수
// 8자 모양 그래프의 수

// 새로운 정점에게 모든 그래프에 연결됨 
// 그렇다면 bfs를 돌려보자

// 새로운 정점 확인용
int inde[1000002];
int outde[1000002];

// 실제 탐색용 코드
vector<int> graph[1000002];
// 정답을 저장할 코드
vector<int> answer(4);

void bfs(int start)
{
    // {정점, 거리} 를 저장한다.
    queue<pair<int, int>> que;
    que.push({ start, 0 });

    bool isVisited = false;
    int cnt = 0;

    while (!que.empty())
    {
        auto [cur, dist] = que.front();
        que.pop();

        if (isVisited)
        {
            // 만약 사이클이 있는 상태에서 
            // n - 1 번 돌았다면 도넛, 아니라면 8자이다.
            cnt == dist ? ++answer[1] : ++answer[3];
            return;
        }

        for (int edge : graph[cur])
        {
            // 사이클이 있다면 true 
            if (start == edge)
                isVisited = true;
                
            que.push({ edge, dist + 1 });
            ++cnt;
        }
    }

    // 만약 사이클이 없다면 막대 그래프
    ++answer[2];
}


vector<int> solution(vector<vector<int>> edges) 
{
    int maxNode = 0;
    
    for (const auto& edge : edges)
    {
        ++inde[edge[1]];
        ++outde[edge[0]];
        graph[edge[0]].push_back(edge[1]);
    }
    
    for(int i = 1; i < 1000002; ++i)
    {
        // 들어오는 간선이 없고, 최소 2개의 정점이 빠져나간다면 새로운 정점이다.
        if(inde[i] == 0 && outde[i] >= 2)
        {
            answer[0] = i;
            break;
        }
    }
    
    vector<int> course = graph[answer[0]]; 

    for(int i = 0; i < course.size(); ++i)
        bfs(course[i]);
    
    return answer;
}