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

1325번: 효율적인 해킹

---

 

BFS를 이용하여 풀면 된다. 이상하게 DFS로 풀면 메모리 초과가 난다. 화가난다...

A와 B가 서로를 가리킬 수 있다는 점을 주의하자!

 

1. 간선 입력을 arr에 받아준다.
2. bfs를 통해 방문여부(visited)를 체크하면서 연결되어있는 컴퓨터 개수를 찾는다.
3. 컴퓨터 수가 최대라면 answer 배열 초기화 해주고 아니면 append 해준다.

 

import sys
from collections import defaultdict, deque
input = sys.stdin.readline

arr = defaultdict(list)
N, M = map(int, input().split())

for _ in range(M):
    s, e = map(int, input().split())
    arr[e].append(s)

def bfs(x):
    visited = [False]*(N+1)
    visited[x] = True
    queue = deque([x])
    cnt = 1
    while queue:
        x = queue.popleft()
        for i in arr[x]:
            if not visited[i]:
                visited[i] = True
                cnt+=1
                queue.append(i)
    return cnt

_max = 0
answer = []
for i in range(1, N+1):
    result = bfs(i)
    if result > _max:
        _max = result
        answer = [i]
    elif result == _max:
        answer.append(i)

print(*answer)