#1325 효율적인 해킹(DFS)

이번 문제는 Silver II 난이도의 문제입니다.  저는 처음에 너무 단순하게 생각해서 한번 틀렸네요.  신뢰관계의 종속성이라는 문제때문인데요.  A 가 B를 신뢰하고, B가 C를 신뢰하면, A가 C를 신뢰한다는 사실입니다.  이에 대한 이해도가 틀리면, 해결방법도 당연히 틀리겠죠.

 

문제의 요지를 살펴보면, N개의 컴퓨터들이 있고, M개의 신뢰관계가 존재할 경우에, 신뢰를 받는 최상위 컴퓨터를 찾는 것입니다.  예를 들면 다음의 그림과 같이 5대의 컴퓨터가 있고, 4개의 신뢰관계가 주어졌다고 해보죠.

 

Trust Network

화살표 방향으로 신뢰관계가 주어집니다.  E는 C를 신뢰하고, C는 A와 B를 신뢰합니다.  직관적으로 보면, 저 위의 그림의 경우에 A 또는 B를 해킹하면, 총 4대의 컴퓨터를 한번에 해킹할 수 있습니다.

 

전 이 문제를 화살표를 거꾸로 해서, DFS를 사용하여 해결했습니다.  동적 프로그래밍을 가미하면 조금 더 나이스한 솔루션이 되었을것이지만, 그렇게 하지 않고, 모든 노드들에 대해서 DFS를 실행해서 AC를 받았습니다.  DFS 알고리즘이 \(O(N)\)이므로, 제가 작성한 알고리즘은 \(O(N^2)\)인 셈입니다.  노드수가 최대 10,000개에 시간제한이 5초였기 때문에 AC를 받았죠.  만약 시간초과가 났다면, 동적 프로그래밍을 적용해서 제출을 했을겁니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//--------------------------------------------------------------------
//  baekjoon #1325 - Effective hacking
//    - by Aubrey Choi
//    - created at 2019-07-02
//--------------------------------------------------------------------
#include <stdio.h>
#include <vector>

int v[10000], c[10000], t;
std::vector<int> adj[10000];
int dfs(int s) { v[s]=t; int r=1; for(auto k:adj[s]) if(v[k]!=t) r+=dfs(k); return r; }
int main()
{
  int n, m, a, b, max=0;
  scanf("%d%d", &n, &m);
  while(m--) { scanf("%d%d",&a,&b); adj[b-1].push_back(a-1); }
  for(int i=0; i<n; i++) t=i+1, c[i]=dfs(i), max=(c[i]>max)?c[i]:max;
  for(int i=0; i<n; i++) if(c[i]==max) printf("%d ",i+1); putchar('\n');
}