BFS 1325번 효율적인 해킹

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

1325번: 효율적인 해킹

오늘은 백준 문제 중 1325번 효율적인 해킹 문제를 해결해보았다. 해당 문제는 한번의 해킹으로 최대한 많은 컴퓨터를 해킹하기를 원한다. 각 컴퓨터는 신뢰 관계가 있는데 만약 신용 받는 컴퓨터를 해킹하면 신용하는 컴퓨터는 자동으로 해킹이 된다. 

 

해당 문제의 특징은 그래프가 일반 그래프가 아니라는 점과 한번에 가장 많은 수의 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 리턴해주어야 한다는 특징이 있다.

 

from collections import deque

n, m = map(int, input().split())
adj = [[] for _ in range(n+1)]

for _ in range(m):
    x, y = map(int, input().split())
    adj[y].append(x)
    
def bfs(v):
    q = deque([v])
    visited = [False] * (n+1)
    visited[v] = True
    count = 1
    while q:
        v = q.popleft()
        for e in adj[v]:
            if not visited[e]:
                q.append(e)
                visited[e] = True
                count += 1
    return count
    
result = []
max_value = -1

for i in range(1, n+1):
    c = bfs(i)
    if c > max_value:
        result = [i]
        max_value = c
    elif c == max_value:
        result.append(i)
        max_value = c
for e in result:
    print(e, end=" ")