GraphTraversal_효율적인 해킹(1325)

문제

풀이

• DFS는 recursion error 나서 BFS로 풀었다..
• 그리고 제출시 python3는 오류나서 pypy로 고쳐서 냈다.
• 그리고 BFS return 값을 변수로 해야했다. 만약 배열로 하면 또 시간 초과 나더라..
• Node의 수가 정해진 경우 BFS에서는 가능하면 HashSet보다는 boolean array를 사용하는 것이 시간초과가 덜 난다고 하더라..

코드

from collections import deque
import sys

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

if __name__ == "__main__":
    N, M = map(int, input().split())
    arr = [[] for _ in range(N+1)]
    maxN = 0
    res = []
    for i in range(M):
        a, b = map(int, input().split())
        arr[b].append(a)

    for i in range(1, N+1):
        ans = BFS(i, arr, N)
        if ans > maxN:
            maxN = ans
            res.clear()
            res.append(i)
        elif ans == maxN:
            res.append(i)

    print(*res)

느낀 점

• 만약 참고 블로그가 없었다면 그래프탐색을 밀고 나갔을까..
  아주 사소한 것으로 시간 초과를 고칠 수 있는 것이 무엇인지에 대한 지식이 아직 없었다.
  

고생 ..