[백준/1325] 효율적인 해킹 (Python)

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

1325번: 효율적인 해킹

 

Difficulty : Silver 1

 

Status : Solved

 

Time : 00:21:11

 

---

 

문제 설명

 

 

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

 

출력

 

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

 

입력 예시

 

5 4
3 1
3 2
4 3
5 3

 

출력 예시

 

1 2

 

 

---

 

풀이

 

너무 복잡하게 꼬아 생각해서 생각보다 시간이 오래 걸렸다. 단순하게 생각하면 되는 것을...

 

1부터 N까지 모든 경우에서, 이 노드를 출발지로 삼았을 때 방문할 수 있는 모든 노드의 개수를 알아내면 된다. 즉 그래프 탐색을 N번에 걸처 수행하면 될 문제이다.

 

단, 재귀로 구현할 경우 이미 방문한 노드로의 재방문(노드로 가는 경로가 둘 이상인 경우)에 유의하도록 하자.

 

풀이 코드

from collections import defaultdict
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
edge_dict = defaultdict(list)

def dfs(node) :
  visited = [False]*N
  visited[node] = True
  q = [node]
  cnt = 1

  while q :
    node = q.pop()
    for nxt in edge_dict[node] :
      if not visited[nxt] :
        visited[nxt] = True
        cnt += 1
        q.append(nxt)
    
  return cnt
    
for _ in range(M) :
  A, B = map(int, input().split())
  edge_dict[B-1].append(A-1)

answer, maxlen = [], 0
for i in range(N) :
  tmp = dfs(i)
  if tmp > maxlen :
    answer, maxlen = [i+1], tmp
  elif tmp == maxlen :
    answer.append(i+1)
print(*answer)

풀이 완료!