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

문제 링크 : https://www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

 

A가 B를 신뢰할때 컴퓨터 B를 해킹하면 컴퓨터 A를 해킹할 수 있다.

이는 A B 이런식으로 입력으로 주어진다.

 

이 관계는 그래프로 표현할 수 있다.

B를 해킹하면 A를 해킹할 수 있으므로 B를 통해 A로 갈 수 있다고 생각했다.

그래서 입력 예제1을 그래프로 표현하면 아래와 같다.

입력 예제1

5 4

3 1

3 2

4 3

5 3

그림이 너무 이쁘다....

 

그래서 1번과 2번을 해킹했을 때 총 4개의 컴퓨터를 해킹할 수 있으므로 답이 된다.

이 그래프의 관계를 인접리스트로 받아서 각 점에서 시작하는 BFS를 돌리고 가장 많이 해킹한 인덱스를 구하면 된다.

 

from sys import stdin
from collections import deque

input = stdin.readline

n,m = map(int, input().split())

adj_list = [[] for _ in range(n)]
visited = [0]*n
visited_num = 0

for _ in range(m):
    a,b = map(int, input().split())
    adj_list[b-1].append(a-1)
def solv():
    global visited_num
    max_cnt = 0
    max_idx = []
    for start in range(n):
        visited_num += 1
        cnt = bfs(start)
        if max_cnt < cnt:
            max_cnt = cnt
            max_idx = [start+1]
        elif max_cnt == cnt:
            max_idx.append(start+1)

    print(*max_idx)
def bfs(start):
    global visited
    q = deque([start])
    visited[start] = visited_num

    cnt = 0
    while q:
        now = q.pop()
        cnt += 1

        for nxt in adj_list[now]:
            if visited[nxt] != visited_num:
                visited[nxt] = visited_num
                q.appendleft(nxt)
    return cnt
solv()