[Baekjoon] DFS/BFS - 1325 효율적인 해킹

문제

1325번: 효율적인 해킹

 

풀이

PyPy3로 제출할 것

"""
5 4
3 1
3 2
4 3
5 3

5 5
5 4
4 3
3 2
2 1
1 5

5 5
5 4
4 3
3 2
2 1
1 4
"""
# 정답률이 낮은 이유는 문제의 난이도가 어렵기 때문이 아닌, 시간 초과 등의 이유 때문이다.

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().rstrip().split())
nodes = [[] for _ in range(n + 1)]
for _ in range(m):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    # 반대방향으로 화살표를 설정한다.
    # 이 후 y에서 시작했을 때 탐색한 컴퓨터의 개수를 저장한다
    nodes[y].append(x)


def solution(nodes):
    result = []
    max_value = 0

    for i in range(1, n + 1):
        count = bfs(nodes, i)
        result.append((i, count))
        max_value = max(max_value, count)

    for index, count in result:
        if count == max_value:
            print(index, end=" ")
    print()


def bfs(nodes, start):
    queue = deque([start])
    # 시작점마다 visited를 새로 선언한 후 탐색한 컴퓨터의 개수를 구한다.
    visited = [False] * (n + 1)
    visited[start] = True
    count = 1

    while queue:
        now = queue.popleft()

        for v in nodes[now]:
            if not visited[v]:
                queue.append(v)
                visited[v] = True
                count += 1

    return count


solution(nodes)

 

채점 결과