백준 문제 풀이 - 효율적인 해킹 1325번

📜 문제 이해하기

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.
이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.
이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

💡 문제 재정의

단방향 그래프가 주어질 때 최대 갯수로 이어진 노드들을 출력하라.

✏️ 계획 수립

이 문제는 dfs를 사용하면 풀 수 있다.
먼저 단방향 인접 리스트를 구성하고 각 노드별로 dfs를 돌려서 가장 많은 노드를 거치는 노드를 출력하면 된다.

💻 계획 수행

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> adj_list(100001);
bool visited[100001];
int this_cnt;

void dfs(int current_node){
    this_cnt++;
    visited[current_node] = true;
    for (const int &next_node : adj_list[current_node])
        if (!visited[next_node])
            dfs(next_node);
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;
    int max_cnt = -1;
    vector<int> result;
    cin >> N >> M;

    for (int i=0;i<M;i++){
        int u, v;
        cin >> u >> v;
        adj_list[v].push_back(u);
    }

    for (int i=1;i<=N;i++){
        memset(visited, false, N + 1);
        this_cnt = 0;
        dfs(i);
        if (this_cnt > max_cnt){
            result.clear();
            result.push_back(i);
            max_cnt = this_cnt;
        }
        else if (this_cnt == max_cnt)
            result.push_back(i);
    }

    for (const int &num : result)
        cout << num << " ";
    return 0;
}

🤔 회고

사실 처음에는 파이썬으로 이 문제를 해결했지만 처음에는 RecursionError가 발생했고 sys 모듈로 해결을 해도 도저히 메모리 초과, 시간초과를 해결할 수가 없었다. DP와 같은 기법을 써도 도저히 안되서 C++로 구현해 해결하였다. C++로도 3365ms가 나와 간신히 시간에 맞춘것을 보면 성능이 좋은 언어를 사용해야 하는 문제였다고 생각한다.