[C++][통신망 분석] 구름톤 챌린지 4주차 학습 일기 (1)

서론

진짜 순수 문제 풀이 시간만 5시간은 걸렸다.

이렇게 어렵게 풀 문제였나 생각이 들어서 마음이 심란했던 하루다.

2일 차 통신망 분석

문제 : 그래프에서 연결된 것들의 집합 중  가장 밀도가 높은 컴포넌트의 정보를 구하자.

 

간선을 2차원 배열 edge에 받아 저장해 주었다.

빠른 시간 복잡도를 위해서 각 노드(i)에서 갈수 있는 노드(j)를 저장해 주었다.

edge

연결된 것들의 집합을 DFS를 통하여 구하고(밀도를 구하기 위해 간선의 갯수도 구하고), realComponent에 저장해주었다.

출력 조건을 맞추기 위해서 realComponent배열 앞에

밀도와 (컴퓨터의 수 * -1) 마지막으로 (컴포넌트에서 가장 작은 수* -1)

를 넣어주고 내림차순으로 정렬하여 realComponent[0]에 있는 값을 출력하였다.

 

◆코드 전문◆

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
int N, M;

void dfs(vector<vector<int>> &edge, vector<int> &belongComponent,
         vector<int> &countEdge, vector<vector<double>> &realComponent,
         int current, int componentNumber)
{
    if (belongComponent[current] != 0)
        return;

    belongComponent[current] = componentNumber;
    realComponent[componentNumber].push_back(current);

    for (int j = 0; j < edge[current].size(); j++)
    {
        countEdge[componentNumber]++;
        dfs(edge, belongComponent, countEdge, realComponent, edge[current][j], componentNumber);
    }

    return;
}

int main()
{
    cin >> N >> M;

    vector<vector<int>> edge(N + 1, vector<int>{});
    vector<int> belongComponent(N + 1);
    vector<int> countComponent(N + 1);
    vector<int> countEdge(N + 1);
    vector<vector<double>> realComponent(N + 1, vector<double>{});
    for (int i = 0; i < M; i++)
    {
        int bufA, bufB;
        cin >> bufA >> bufB;
        edge[bufA].push_back(bufB);
        edge[bufB].push_back(bufA);
    }

    // realComponent에 node 저장
    int componentNumber = 1;
    for (int i = 1; i < edge.size(); i++)
    {
        if (belongComponent[i] == 0)
        {
            dfs(edge, belongComponent, countEdge, realComponent, i, componentNumber);
            componentNumber++;
        }
    }

    for (int i = 0; i < realComponent.size(); i++)
    {
        sort(realComponent[i].begin(), realComponent[i].end());
    }

    // sort를 하기 위해 density, -size, -small 을 insert
    for (int i = 1; i < realComponent.size(); i++)
    {
        if (realComponent[i].size() == 0)
            continue;
        if (countEdge[i] == 0)
        {
            while (!realComponent[i].empty())
            {
                realComponent[i].pop_back();
            }
            continue;
        }

        double density = countEdge[i] / (double)realComponent[i].size();
        int size = -realComponent[i].size();
        int small = 1e8;
        for (int k = 0; k < realComponent[i].size(); k++)
        {
            small = min(small, (int)realComponent[i][k]);
        }
        small = -small;

        vector<double>::iterator it;
        it = realComponent[i].begin();
        realComponent[i].insert(it, small);
        it = realComponent[i].begin();
        realComponent[i].insert(it, size);
        it = realComponent[i].begin();
        realComponent[i].insert(it, density);
    }

    sort(realComponent.begin(), realComponent.end(), greater<>());
    for (int i = 3; i < realComponent[0].size(); i++)
    {
        cout << realComponent[0][i] << " ";
    }
}

 

 

어려웠던 점

처음에 입력 값의 숫자가 크길래 인접 리스트로 짰는데 타임아웃이 떠서 인접행렬로 짯다가 계산해보니 인접리스트로 가능할꺼 같아다시 짯다.

그래프 문제는 풀어봤지만 구현이 익숙하지 않아서 1시간동안 테스트 코드를 만들었다. 결과는 Fail과 Timeout

그래서 잘못된 부분을 고치니 1시간이 또 지났다. Fail은 고쳤지만, 없어지지 않는 Timeout...

하지만, 내실력으로 어디서 시간복잡도가 꼬였는지 알지 못해서 bfs로도 바꾸어서 계산해보고, 줄일 수 있는 부분을 줄여봤음에도 Timeout이 발생해서 만든 코드를 싹 지우고 다시 풀었다.

지우고 코드를 다시 썻으니 잘 써지길 기대했지만, 또 Fail과 Timeout을 만나게 되었고, 화가나서 bfs까지만 계산하고 테스트를 제출했더니, Timeout이 뜨는게 아닌가? 이점을 착안해서 인접 리스트 구현 방식과 DFS구현 방식을 손을 봤고, 아래 작업도 간략화 하였다. 그러니 하루가 다 가있는게... 얻은것은 있지만 뒤처진다는 생각이 드는 하루였다.

 

배운 점

Timeout이 나올 경우 어느 로직에서 나온지 확인이 어렵다면, 적절히 코드를 잘라서 어느 부분이 시간을 많이 잡아먹는지에 대한 TestCase 응용 법이 있다는 것을 알게 되었다.

또한 변수명을 이해할 수 있게 정의함으로써, 긴 코드에서 프로그래머가 변수의 의미를 잃어버리지 않게 하는것이 코드를 작성하면서 좋게 느껴졌습니다.

느낀 점

어려운점, 서론에도 말했지만, 구름톤이 4주차가 되가면서 어려운 문제가 나오고 그중에서 내가 취약한 부분인 그래프 문제가 나옴으로 인해서 힘든거 같다.

하지만 이런 고통도 언젠가 실력에 밑거름이 되리라 믿고...(아니 되야되...) 내일도 열심히 구름톤 문제를 풀어야겠다.