효율적인 해킹

가장 중요한 부분

DFS를 통해서 풀단고 가정을 할 때 최악의 경우에는 O(N^2)의 시간 복잡도라 최대의 시간복잡도는 1억이다.

(최악의 경우 DFS를 1억번 호출한다는 말이다)
(근데 시간 이 5초라서 이런거 생각을 안했었다)

그러면 일단 내가 구현한 부분이 틀린것인가? 라고 먼저 생각을 하고 최선의 방법을 찾아야한다.

일단 도식화를 하면서 입력예제를 이해할려고했다.

처음에는 뭔말인가 싶었는데 출력결과랑 도식화 한것이랑 계속 비교하고 문제는 이해를 함.

중간에 도식화 과정에서 그래프 모양인것을 확인을 함.

그리고 이 그래프를 어떻게 코드로 구현할지

"인접행렬"이랑 "인접 리스트" 둘중 하나를 골라야했는데

나에게 좀더 친숙한 인접리스트를 사용하기로 함.

그리고 이 문제는 map(좌표)문제가 아니라서 visited를 초기화 해주긴 해야하지만 dy, dx같은 것은 필요없었다.

그래프 문제이기 때문에 탐색을 할 때는 DFS를 통해 int형을 반환할 수 있도록 조금 변경했다.

(DFS의 반환값에서 시간이 좀 걸렸다.)

이해 안가는 부분

조금 어렵? 이해가 안가는 부분은 sort할 때

pair가 들어와서 이것을 first는 오름차순으로 second는 내림차순으로 구현을 하고 싶어서 cmp함수를 따로 만들었는데

bool cmp(const pair<int, int>& a, const pair<int, int>& b)
{
    if (a.first == b.first)
    {
        return a.second > b.second;
    }
    return a.first < b.first;
}

이렇게 하면 왜 first는 오름차순으로 정렬이되고 second는 내림차순으로 정렬이 되는지 모르겠다.

cpp 내코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl "\n"
#define MAX 10002

int n, m, n1, n2, ret = 0;
vector<vector<int>> adj;
vector<int> visited;
vector<pair<int, int>> vec;

bool cmp(const pair<int, int>& a, const pair<int, int>& b)
{
    if (a.first == b.first)
    {
        return a.second > b.second;
    }
    return a.first < b.first;
}

int DFS(int here)
{
    int cnt = 1;
    visited[here] = 1;
    for (int there : adj[here])
    {
        if (visited[there]) continue;
        cnt += DFS(there);
    }
    return cnt;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m;
    adj.resize(MAX);
    visited.resize(MAX);
    for (int i = 1; i <= m; ++i)
    {
        cin >> n1 >> n2;
        adj[n2].push_back(n1);
    }
    for (int i = 1; i <= n; ++i)
    {
        vec.push_back({ DFS(i), i} );
        fill(visited.begin(), visited.end(), 0);
    }
    std::sort(vec.begin(), vec.end(), cmp);
    reverse(vec.begin(), vec.end());
    int Max = vec[0].first;
    for (pair<int, int> p : vec)
    {
        if (Max == p.first)
            cout << p.second << " ";
    }
    
    return 0;
}

전역 변수로 구현

이런식으로 그래프가 있을 경우 아래처럼 구현이 가능함.

int DFS()

int형을 반환하는 dfs를 꼭 기억해야한다.

이런식으로 타고 올라가는 거임.