백준 1325번: 효율적인 해킹

BOJ

백준 1325번: 효율적인 해킹

접근

A가 B를 신뢰한다. B를 해킹하면 A도 해킹할 수 있지만, A를 해킹하면 B를 해킹할 수 있지 않다. 이러한 흐름은 양방향 그래프가 아닌 단방향 그래프로 문제를 해결할 수 있다.

BFS와 DFS의 시간복잡도는 O(V+E)로 같다. 문제의 유형에 따라 적합한 방식을 사용하면 된다. 이 문제는 최단거리를 찾는 게 아니고 1만개의 정점들끼리의 관계를 탐색해야 하기 때문에 BFS가 더 효율적일 수 있다.

Python3로 제출하면 시간 초과가 발생해서 Pypy3로 제출했다.

Correct Solution

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

N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]


def bfs(v):
    D = 0
    q = deque()
    q.append(v)

    visit = [False] * (N + 1)
    visit[v] = True
    while q:
        now = q.popleft()
        for i in graph[now]:
            if not visit[i]:
                visit[i] = True
                q.append(i)
                D += 1
    return D


for i in range(M):
    a, b = map(int, input().split())
    graph[b].append(a)

max_value = 0
result = []
for i in range(1, N + 1):
    if graph[i]:
        temp = bfs(i)
        if max_value < temp:
            max_value = temp
            result = [i]
        elif max_value == temp:
            result.append(i)

print(*result)