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

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

프로그래머스

 

매번 프로그래머스 문제를 풀면서 느끼는 건 왤캐 어렵냐... 진짜로!!

 

새롭게 추가되는 정점은 다음과 같은 조건이 있다.

• 이 그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했습니다.

즉, 새로운 정점은 들어오는 간선은 없고, 뻗어나가는 간선만 존재한다.

 

그래서 처음 그래프 정보를 edges로 받을 때 inNode, outNode를 직접 세면서 answer[0]을 찾을 수 있다.

• answer[0] = 새로운 정점 숫자
• answer[1] = 도넛 모양 그래프 개수
• answer[2] = 막대 모양 그래프 개수
• answer[3] = 8자 모양 그래프 개수

for(int i=1;i<INF;i++) {
    if(inNode[i] == 0 && outNode[i] >= 2) {
        answer[0] = i;
        break;
    }
}

// answer[0] = 새로운 정점 숫자

 

새로운 정점을 찾았다.

 

이제 이렇게 생각해볼 수 있다.

 

새로운 정점이 향하는 정점은 [도넛, 막대, 8자] 그래프 중 하나의 정점이다.

• 이 점을 B라고 할 때, 우리는 B를 기준으로 BFS || DFS를 사용해서 이 그래프가 어떤 그래프인지 확인해볼 수 있다.

막대는 뭐 bfs가 더 이상 못 뻗어나갈 때로 생각해볼 수 있는데

 

도넛, 8자는 어떻게 구분할까?

• 문제에서 주어진 입출력 예제/그래프 그림을 보고서 아래와 같은 조건을 떠올렸다.
• 사이클인데 n-1번 돌면 도넛 / 아니면 8자다.

---

전체 코드

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

#define INF 1000002

using namespace std;

int inNode[INF];
int outNode[INF];

vector<int> graph[INF];

vector<int> solution(vector<vector<int>> edges) {
    vector<int> answer(4);
    
    for(const auto& edge : edges) {
        inNode[edge[1]]++;
        outNode[edge[0]]++;
        graph[edge[0]].push_back(edge[1]);
    }
    
    for(int i=1;i<INF;i++) {
        if(inNode[i] == 0 && outNode[i] >= 2) {
            answer[0] = i;
            break;
        }
    }
    
    for(int i=0;i<graph[answer[0]].size();i++) {
        int start = graph[answer[0]][i];
        // cout << start << "\n";
        
        queue<pair<int, int>> q;
        q.push(make_pair(start, 0));
        
        bool isVisited = false;
        int cnt = 0;
        while (!q.empty()) {
            pair<int, int> pr = q.front();
            q.pop();
            
            if (isVisited) {
                // 사이클인데 n-1번 돌면 도넛
                if (cnt == pr.second) {
                    answer[1]++;
                } else {
                    answer[3]++;
                }
                break;
            }
            
            for (int j : graph[pr.first]) {
                if (start == j) {
                    isVisited = true;
                }
                q.push(make_pair(j, pr.second + 1));
                cnt++;
            }
        }
        
        if (!isVisited) {
            answer[2]++;
        }
    }
    
    return answer;
}