[PS] 2024 카카오 겨울 인턴십 - 도넛과 막대 그래프

프로그래머스

문제

- 난이도: Level 2

- 문제 설명: 추가 정점과 그래프들의 개수 구하기

 

풀이

언뜻 보면 복잡해보이지만,

문제에서 정점과 간선의 수를 상세하게 주어주는 것을 보면

정점과 간선을 파악해서 규칙을 찾는 것이 첫 접근법이라는 것을 알 수 있다.

 

연결된 간선들이 주어졌으므로 그래프를 만들고, 추가 정점을 찾는다.

추가 정점을 기준으로 뻗어나간 간선에서 각 그래프를 전부 방문한 뒤,

정점과 간선의 개수에 따라 그래프의 종류를 판별한다.

그래프만 잘 파악한다면 쉽게 풀 수 있는 문제다.

 

입출력 예#2를 살펴보면서

각 그래프들의 구조 특징을 파악해보자

예시

edges	result
[[4, 11], [1, 12], [8, 3], [12, 7], [4, 2], [7, 11], [4, 8], [9, 6], [10, 11], [6, 10], [3, 5], [11, 1], [5, 3], [11, 9], [3, 8]]	[4, 0, 1, 2]

 

1. 추가 정점

이 문제에서 추가 정점은 4이다.

4에서 나가는 간선만 있고 4로 들어오는 간선은 없다.

그래프는 최소 2개 있으므로 나가는 간선은 2 이상이다.

따라서 나가는 간선이 2 이상이고 들어오는 간선이 없는 정점이 추가 정점임을 알 수 있다.

 

2. 도넛 그래프

도넛 그래프는 사이클을 가지고,

정점의 개수는 간선의 개수이다.

 

3. 막대 그래프

가장 간단한 막대 그래프다.

정점의 개수는 간선의 개수 + 1이다.

 

4. 8자 그래프

8자 그래프는 도넛 그래프에 정점을 하나 추가해서 연결한 것이다.

사이클을 가지고, 정점의 개수는 간선의 개수 - 1이다.

구조 특징

도넛	정점의 개수 = 간선의 개수
막대	정점의 개수 = 간선의 개수 + 1
8자	정점의 개수 = 간선의 개수 - 1
생성 정점	나가는 간선의 개수 2 이상, 들어오는 간선의 개수 0

 

구조 특징을 파악하여 그래프의 종류를 알아낼 수 있으므로,

이제 그래프를 돌면서 들어오는 간선, 나가는 간선의 개수를 세면 된다.

 

코드

1. 정확성 47 오답 코드

오답 코드에서는 나가는 간선과 들어오는 간선으로 계산하지 않고,

나가는 간선만 있는 경우를 시작 정점으로 생각했다.

하지만 막대 그래프의 시작 정점의 경우도 동일하기 때문에,

나가는 간선과 들어오는 간선의 개수로 구분해야 하기 때문에 오답이었다.

 

또, 정점 기준으로만 방문 여부를 판단했기 때문에

오답이 나오는 것이었다.

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

void dfs(int cur, unordered_map<int, vector<int>>& graph, 
 unordered_map<int, bool>& isVisited, int& nodeCnt, int& edgeCnt) {
    if (isVisited[cur]) return;
    
    // 방문 체크, 정점 카운트
    isVisited[cur] = true;
    nodeCnt++;
    
    // 현재 정점에서 나가는 간선들 방문, 카운트
    for (int next : graph[cur]) {
        edgeCnt++;
        dfs(next, graph, isVisited, nodeCnt, edgeCnt);
    }
}

vector<int> solution(vector<vector<int>> edges) {
    // [추가 정점 번호, 도넛, 막대, 8자]
    vector<int> answer;
    int createNode = 0, donut = 0, stick = 0, eight = 0;
    
    unordered_map<int, vector<int>> graph;
    unordered_map<int, bool> isVisited;
    unordered_map<int, bool> inEdge; // 들어오는 간선이 없으면 추가 정점
    
    // 그래프 기록
    for (auto& e : edges) {
        graph[e[0]].push_back(e[1]);
        inEdge[e[1]] = true;
    }
    
    // 생성한 정점 찾기
    for (auto& g : graph) {
        int key = g.first;
        if (inEdge[key] == false) {
            createNode = key;
            break;
        }
    }

    for (int next : graph[createNode]) {
        if (isVisited[next]) continue;
        
        int nodeCnt = 0, edgeCnt = 0;
        dfs(next, graph, isVisited, nodeCnt, edgeCnt);
        
        // 그래프 탐색 종료 후 종류 판별하기
        if (nodeCnt == edgeCnt) donut++;
        else if (nodeCnt - 1 == edgeCnt) stick++;
        else eight++;
    }
    
    answer.push_back(createNode);
    answer.push_back(donut);
    answer.push_back(stick);
    answer.push_back(eight);
    return answer;
}

 

2. 제출한 정답 코드

#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

void dfs(int cur, unordered_map<int, vector<int>>& graph, unordered_set<int>& visited, int& nodeCnt, int& edgeCnt) {
    visited.insert(cur);
    nodeCnt++;

    for (int next : graph[cur]) {
        edgeCnt++; // 단방향 간선이므로 그냥 +1
        if (!visited.count(next)) {
            dfs(next, graph, visited, nodeCnt, edgeCnt);
        }
    }
}

vector<int> solution(vector<vector<int>> edges) {
    unordered_map<int, vector<int>> graph;
    unordered_map<int, int> inDegree, outDegree;
    int createNode = 0;, int donut = 0, stick = 0, eight = 0;

    // 그래프 기록
    for (auto& edge : edges) {
        graph[edge[0]].push_back(edge[1]);
        outDegree[edge[0]]++; inDegree[edge[1]]++;
    }

    // 생성한 정점 찾기: inDegree == 0 && outDegree >= 2
    for (auto& [node, outs] : outDegree) {
        if (inDegree[node] == 0 && outs >= 2) {
            createNode = node;
            break;
        }
    }

    unordered_set<int> visited;
    for (int next : graph[createNode]) {
        if (visited.count(next)) continue;

        int nodeCnt = 0, edgeCnt = 0;
        dfs(next, graph, visited, nodeCnt, edgeCnt);

        // 그래프 탐색 종료 후 종류 판별하기
        if (nodeCnt == edgeCnt) {
            donut++;
        } else if (nodeCnt == edgeCnt + 1) {
            stick++;
        } else {
            eight++;
        }
    }

    return {createNode, donut, stick, eight};
}

 

회고

역시 어렵다