[프로그래머스] 도넛과 막대 그래프 (c++) 엣지 케이스

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

프로그래머스

풀이 방법

특정 알고리즘을 사용한다기보단 특징과 조건을 잘 찾고 엣지 케이스만 확인 잘하면 된다.

 

1. 중앙 노드 찾기

먼저 아무 모형과 관련이 없는 중앙 노드를 찾으려고 특징을 살펴보았다.

문제의 제한 사항에 모든 그래프의 수의 합은 2 이상이라는 점에서 들어오는 edge가 없으며, 나가는 edge가 2개 이상인 노드를 중앙 노드라고 판별할 수 있다.

 

2. 각 그래프 구별하기

 

1. 막대 그래프:

• 그래프 내에 나가는 간선(out_edge)이 없는 노드가 존재하면 막대그래프로 구별할 수 있다.

2. 원형 그래프와 8자형 그래프:

• 두 그래프의 주요 차이점은 다음과 같다.

• 원형 그래프: 모든 노드의 나가는 간선(out_edge) 수가 정확히 1개여야 한다.

• 8자형 그래프: 최소한 하나 이상의 노드가 나가는 간선(out_edge) 수가 2개 이어야 한다.

 

이를 판별하기 위해 각 노드를 순회하며 다음과 같은 과정을 수행한다.

• 시작 노드로 되돌아오기 전에 나가는 간선이 2개 이상인 노드가 존재하면 8자형 그래프로 판단한다.

• 만약 그런 노드가 없다면 원형 그래프로 판단한다.

• 순회 도중 나가는 간선이 0개인 노드를 발견하면 해당 그래프는 막대 그래프로 판단한다.

 

코드

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

using namespace std;


vector<vector<int>> graph(1000001);
int out_p[1000001];
int in_p[1000001];
int n, center;
void make_graph(vector<vector<int>> edges) {    
    for (int i = 0;i < edges.size();i++) {
        int a = edges[i][0], b = edges[i][1];
        n = max(a, n);
        n = max(b, n);
        in_p[b] += 1, out_p[a] += 1;
        graph[a].push_back(b);
    }
}

void find_center() {
    int visited[n+1];
    for (int i = 1;i <= n;i++) {
        if (in_p[i] == 0 && out_p[i] > 1) {
            center = i;
            break;
        }
    }
}
int stick = 0, circle = 0, eight = 0;
void cnt_graph() {    
    for (int i = 0;i < graph[center].size();i++) {
        if (out_p[graph[center][i]] == 0) {
            stick++;
            continue;
        }        
        else {
            int start = graph[center][i];
            int now = graph[start][0];        
            int flag = 0;
            if (out_p[start] >= 2) {
                flag = 1;
                eight++;
                continue;
            }
            while(start != now) {
                if (out_p[now] == 0) {
                    flag = 3;// 막대인 경우 
                    break;
                }
                if (out_p[now] >= 2) {
                    flag = 1;                    
                    break;
                }
                now = graph[now][0];
            }
            if(flag == 1) eight++;
            else if (flag == 3) stick++;
            else circle++;
        }        
        
    }
    return ;
}
vector<int> solution(vector<vector<int>> edges) {
    vector<int> answer;
    make_graph(edges);
    find_center();
    cnt_graph(); 
    answer.push_back(center);
    answer.push_back(circle);
    answer.push_back(stick);
    answer.push_back(eight);
    return answer;
}