백준 1325번 : 효율적인 해킹 -BFS, DP를 쓰면 안되는 이유 C++

https://www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

1. 문제설명

입력으로 노드간의 단방향 연결관계가 주어진다.

입력으로 들어오는 노드는 최대 만개 이하, 간선 관계는 10만개 이하다.

 

처음 문제를 봤을 때 시간제한이 5초이고 노드가 최대 만개이므로

단순히 모든 노드에 대해 BFS를 돌릴 때 계산량을 생각해보면

10000*10000 = 1억 정도 되므로 2초정도 있으면 충분히 시간제한에 들어올 거라 생각했다.

 

그런데 정답률이 좀 낮은 걸 보고 이렇게 하면 틀릴까 곰곰히 생각을 해보다가

시간을 줄일수 있는 방법으로 DP를 생각했는데

DP를 사용하면 안된다! 이 문제는 DP를 적용할 수 없는 문제이다.

 

 

 

 

---

 

 

2. DP를 사용하면 안되는 이유

처음에 계산을 줄이는 방법으로

탐색한 노드에서 연결된 노드(신뢰관계에 놓여진 노드)의 수를 저장하는 방식으로

DP를 이용할 수 있지 않을까 생각했다.

 

이는 만약 그래프가 단방향 그래프라면 이용할 수 있다.

그림을 보면 쉽게 이해할 수 있다.

 

백준 1325 설명

위 그림과 같이 단방향 그래프인 경우 노드3번을 통해 노드 1번과 2번의 값을 구할 수 있는

DP 알고리즘을 이용하면 된다.

 

백주 1325 설명

 

하지만 이 문제에서는 단방향그래프라는 말이 없었기 때문에

빨간색 같은 간선이 존재할 수 있다.

 

이럴 경우 사이클이 생기기 때문에 DP를 이용한다면

3번 노드에서 값은  3이 나오는데 이때 3에는 1번 노드가 포함되어 있고,

또 1번 노드를 3번 노드 기반해서 값을 구하면 자기 자신을 포함한 채

실제정답은 3인데 4가 되버리는 현상이 나타난다.

 

그렇기 때문에 DP를 이용할 수 있는지 없는지

그래프의 특성을 잘 생각해봐야 올바르게 풀 수 있는 문제였다.

 

이렇게 그냥 무지성으로 DP를 푸는게 아니라

어떻게 풀어야할지 사고과정을 배울 수 있는 좋은 문제인 것 같다.

 

 

---

 

 

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m;
int mem[10001];
vector<int> adj[10001];

int BFS(int x){
    int ret = 0;
    bool vis[n+1];
    memset(vis,0, sizeof(vis));

    queue<int> Q;
    Q.push(x); vis[x] = 1;

    while(!Q.empty()){
        int cur = Q.front(); Q.pop();
        for(auto nx : adj[cur]){
            if(!vis[nx]){
                ret++;
                vis[nx]=1;
                Q.push(nx);
            }
        }
    }

    return ret;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;

    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;

        adj[b].push_back(a);
    }


    int ans = 0;
    for(int i=1; i<=n; i++){
        mem[i] = BFS(i);
        ans = max(ans, mem[i]);
    }

    for(int i=1; i<=n; i++){
        if(mem[i] == ans){
            cout << i << ' ';
        }
    }


    return 0;
}

백준 1325