[Python] 백준 1325 - 효율적인 해킹 문제 풀이

Overview

BOJ 1325번 효율적인 해킹 Python 문제 풀이
분류: Graph Traversal (그래프 탐색), bfs

---

문제 페이지

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

---

풀이 코드

from sys import stdin
from collections import defaultdict, deque


def bfs(start: int, n: int, graph: defaultdict[int]) -> int:
    visit = [False] * (n + 1)
    cnt = 0
    dq = deque([start])
    visit[start] = True
    while dq:
        node = dq.pop()
        for neighbor in graph[node]:
            if not visit[neighbor]:
                visit[neighbor] = True
                dq.append(neighbor)
                cnt += 1
    return cnt


def main():
    def input():
        return stdin.readline().rstrip()

    n, m = map(int, input().split())
    graph = defaultdict(list)
    for _ in range(m):
        a, b = map(int, input().split())
        graph[b].append(a)

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

    print(*sorted(res), sep=' ')


if __name__ == "__main__":
    main()

pypy3 채점 결과 통과하였다. bfs를 이용하여 해킹 가능한 컴퓨터 개수를 파악하여 답을 구한다.

그래프가 양방향이 아닌 단방향 이기 때문에 유니온 파인드를 사용할 수 없고, dfs를 이용하면 메모리 초과가 발생한다.