[Python/파이썬] 백준 1325 - 효율적인 해킹

문제 설명

---

풀이 코드

가장 핵심은 "A가 B를 신뢰한다."는 즉, "B는 A의 부모 노드"이라는 점이다.

 

아래 그림은 위의 "예제 입력 1"에 해당하는 값대로 노드를 표현한 그림이다.

만약 1번 노드에서 시작한다면 3, 4, 5 총 3개의 노드를 탐색하는 것이고

3번 노드에서 시작한다면 4, 5를 탐색하는 것이 된다.

탐색 노드	1번	2번	3번	4번	5번
탐색 수	3	3	2	0	0

 

1. 먼저 입력값을 받아, 노드 연관관계 리스트를 만든다.
2. 각 노드마다 bfs 탐색을 시작해 해당 노드에서 시작하여 총 몇개의 노드를 탐색하는지 카운팅하여 리스트에 저장한다.
3. 가장 많은 노드를 탐색한 노드를 출력한다.

 

정답 코드

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

n, m = map(int, input().split())
relationship = [[] for _ in range(n + 1)]

# A가 B를 신뢰한다. (노드로 표현하면 B는 A의 부모이다.)
for _ in range(m):
    A, B = map(int, input().split())
    relationship[B].append(A)

def bfs(start):
    q = deque()
    q.append(start)
    cnt = 0

    visited = [False] * (n + 1)
    visited[start] = True

    while q:
        cur = q.popleft()
        for next in relationship[cur]:
            if not visited[next]:
                visited[next] = True
                q.append(next)
                cnt += 1
    return cnt

result = []
for start in range(1, len(relationship)):
    result.append(bfs(start))

for i in range(len(result)):
    if max(result) == result[i]:
        print(i + 1)