[백준] 1325 - 효율적인 해킹 [Python(파이썬)]

문제

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

1325번: 효율적인 해킹

 

풀이

일반적인 그래프 탐색 문제다. BFS+for문을 이용하여 풀 수 있는데, 매 순회마다 visited를 초기화시켜야 하는 것에 주의해야 한다(아래 코드에선 bfs함수 실행시마다 초기화된다). 문제 자체의 난이도는 높지 않았는데도 불구하고 시간/메모리초과로 인해 정답률이 낮다. Python3로 돌리면 메모리초과가 발생하니 PyPy3로 돌려야 한다.

 

코드

import sys
import collections

def bfs(start):
    cnt = 1
    visited = [0 for _ in range(n+1)]
    visited[start] = 1
    queue = collections.deque([start])
    while queue:
        u = queue.popleft()
        for v in g[u]:
            if not visited[v]:
                queue.append(v)
                visited[v] = 1
                cnt += 1
    return cnt

n, m = map(int, sys.stdin.readline().split())
g = collections.defaultdict(list)
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    g[b].append(a)

results = []
max_cnt = 0
for i in range(1, n+1):
    cnt = bfs(i)
    if cnt > max_cnt:
        max_cnt = cnt
    results.append([i, cnt])

for i, cnt in results:
    if cnt == max_cnt:
        print(i, end = ' ')