[programmers] 258711번 - 도넛과 막대 그래프(BFS, 2024 KAKAO WINTER INTERNSHIP)

1. 문제 및 예제

 

 카카오 문제에 신나게 달려들었다가 멘탈 박살났다. 처음 들어갈때는 "이게 왜 LV.2야 ㄷㄷ" 라는 생각이 들었는데, 풀다보니 "이게 왜 LV.2야?" 라는 생각이 계속 들었다. ㅋㅋ 임의로 생성된 노드를 구하는 방법이 진입 간선과 진출 간선의 수를 가지고 구한다는 생각을 하지 못해 결국 남의 풀이를 찾아 보았다. 역시 카카오는 기발한 생각으로 쉽게 문제를 풀 수 있거나 문자열과 같이 미친 집중력과 피지컬을 요구하는 쌩짜 구현 이 둘로 나뉘는 것 같다. 불평 해봤자 달라질 건 없으니 해당 방법으로 임의의 노드를 구하고 각 그래프의 종류를 구했다. 각 그래프의 종류를 구하는 방법은 어렵지 않았다. (솔직히 간선의 수로 다 해결할 수 있는 문제였구나를 나중에 깨달았다.)

---

https://school.programmers.co.kr/learn/courses/30/lessons/258711?language=cpp

프로그래머스

---

2. 풀이과정

 

문제는 다음처럼 나눴다.

1. 임의로 배치된 노드를 구한다.

- 해당 노드를 구하면 이 노드와 연결된 점 부터 탐색을 시작하면 되기에 문제가 수월해 질 것이라고 생각했다.

2. 그래프의 종류를 구한다.

 

다음은 임의의 노드를 구하는 과정이다.

 

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

using namespace std;

vector<int> graph[1000001];
int count_in[1000001] = {0};
int count_out[1000001] = {0};

int get_ans_node(){
    int max_node = 0;
    int max_node_size = -1;
    for(int i = 0; i < 1000001; i++){
        //node is in graph
        if(count_in[i] == 0 && count_out[i] >= 2){
                return i;
        }
    }
    return -1;
}

vector<int> solution(vector<vector<int>> edges) {
    vector<int> answer = {0, 0, 0, 0};
    int ans_node = -1;
    //정점을 구한다.
    
    //create graph
    for(int i = 0; i < edges.size(); i++){
        graph[edges[i][0]].push_back(edges[i][1]);
        
        count_in[edges[i][1]]++;
        count_out[edges[i][0]]++;
    }
    
    int start_node = get_ans_node();
    answer[0] = start_node;
    
    return answer;
}

 

 그냥 진입 간선과 진출 간선을 카운트해주기만 했다. 들어오는 간선인 "진입 간선"의 수가 0이어야한다. 임의로 생성된 노드는 각 그래프를 연결하는 노드이기 때문이다. 그러나 이렇게만으로 판별하면 안된다. 막대 모양 그래프의 시작 노드도 진입 간선의 수가 0이기 때문이다. 따라서 이 노드와의 예외를 두기 위해 진출 간선이 2개 이상이라는 조건도 추가해서 구했다.

 

 다음은 그래프 타입을 구하는 과정이다. 탐색알고리즘은 BFS를 사용했다. 전체 정답 코드를 적어보았다.

 

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

using namespace std;

vector<int> graph[1000001];
int count_in[1000001] = {0};
int count_out[1000001] = {0};

int get_ans_node(){
    int max_node = 0;
    int max_node_size = -1;
    for(int i = 0; i < 1000001; i++){
        //node is in graph
        if(count_in[i] == 0 && count_out[i] >= 2){
                return i;
        }
    }
    return -1;
}

int get_graph_type(int start_node){
    queue<int> q;
    
    if(graph[start_node].size() != 1){
            
        if(graph[start_node].size() == 0)
            return 2;
        else
            return 3;
    }
    
    q.push(graph[start_node][0]);
    
    while(true){
        int node = q.front();
        q.pop();
        if(graph[node].size() != 1){
            
            if(graph[node].size() == 0)
                return 2;
            else
                return 3;
        }
        if(node == start_node)
            return 1;
        
        q.push(graph[node][0]);
        
    }
}

vector<int> solution(vector<vector<int>> edges) {
    vector<int> answer = {0, 0, 0, 0};
    int ans_node = -1;
    //정점을 구한다.
    
    //create graph
    for(int i = 0; i < edges.size(); i++){
        graph[edges[i][0]].push_back(edges[i][1]);
        
        count_in[edges[i][1]]++;
        count_out[edges[i][0]]++;
    }
    
    int start_node = get_ans_node();
    answer[0] = start_node;
    
    for(int i = 0; i < graph[start_node].size(); i++){
        int root_node = graph[start_node][i];
        int graph_type = get_graph_type(root_node);
        answer[graph_type]++;
    }
    
    return answer;
}

 

 각 타입 그래프의 특징을 정하면 다음과 같다.

 

1. 도넛형: 탐색하다가 시작 노드를 만나면 도넛형

2. 막대형: 탐색하다가 진출 간선이 0인 노드를 만다면 막대형

3. 8자형: 탐색하다가 시작 노드를 만나기 전, 진출 간선의 수가 2개인 노드를 만나면 8자형

 

해당 조건만 판별하면 됐다.

 

3. 결어

 

  결국 블로그를 찾아보았지만 손에 익숙해지는 연습의 필요성을 느끼게 되었다. 화이팅!