[python] 백준 1325 : 효율적인 해킹(BFS)

[python] 백준 1325 : 효율적인 해킹(BFS)

1325번: 효율적인 해킹 (acmicpc.net)

1325번: 효율적인 해킹

실버 1

그래프, BFS

---

접근

문제를 잘못 이해해서 삽질을 많이 했다.

'A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.'를 잘 이해해야 한다.

양방향 그래프라는 말이 아니라, A가 B를 가리킬 때, B에서 A로 접근할 수 있는 간선이 존재한다는 말이다.

 

예제입력 부분을 보면

3 1
3 2
4 3
5 3

라고 나오는데 이를 단방향 그래프로 그려내면 다음과 같다.

 

보통 입력값을 3 1로 주면

x, y = map(int, input().split())

graph[x].append(y)의 형태로 3번 노드에 1번 노드를 연결하지만

A가 B를 가리킬 때, B에서 A로 접근할 수 있는 간선이 존재해야하므로 거꾸로 그래프를 넣어줘야한다.

graph[y].append(x)

 

화살표를 향하는 쪽으로 신뢰하기 때문에 신뢰받는 노드가 신뢰하는 노드를 역으로 해킹할 수 있게 된다.

따라서 1, 2노드는 3, 4, 5번을,

3번 노드는 4, 5번을 해킹할 수 있고

4, 5번 노드는 아무도 해킹할 수 없다.

 

코드

시간복잡도가 긴편이므로 Pypy3에 넣어도 간신히 통과한다. 느린 언어로는 아마 통과하지 못할듯?

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

def bfs(node):
    queue = deque([node])
    visited = [0] * (N+1)
    visited[node] = 1
    cnt = 0
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                visited[i] = 1
                queue.append(i)
                cnt += 1
    return cnt

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

for _ in range(M):
    x, y = map(int, input().split())
    graph[y].append(x)

hack = []
max_hack = 0
for i in range(1, N+1):
    h = bfs(i)
    if h > max_hack:
        max_hack = h
    hack.append([i, h])

for i, cnt in hack:
    if cnt == max_hack:
        print(i, end = ' ')

어차피 1번부터 n번까지의 노드를 돌아가면서 bfs를 돌리기 때문에 나오는 순서대로 최댓값에 해당하는 노드를 출력하면 된다.