[백준 1325] 효율적인 해킹

0. 제목

• 백준 1325 효율적인 해킹
• BOJ 1325 효율적인 해킹
• 파이썬 1325 효율적인 해킹
• Python 1325 효율적인 해킹

---

1. 문제

www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

---

2. 풀이

• 각 점의 연결 상태를 adj 배열에 나타낸다.
• bfs 알고리즘을 통해 해킹할 수 있는 컴퓨터의 수를 구한다.
• 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력해야 하므로 max_value의 초기값을 -1로 설정하고 각 점마다 오름차순으로 bfs를 수행한다.
• max_value보다 bfs 결과 값이 크면 갱신해주고 result 배열에 넣어준다. 만약 bfs 결과 값이 max_value와 같으면 result 배열에 값을 추가해준다.
• 결과적으로 result가 구해지면 이미 오름차순으로 값들이 담겨 있기 때문에 그대로 출력해주면 된다.

---

3. 코드

from collections import deque
 
n, m = map(int, input().split())
adj = [[] for _ in range(n+1)]
 
for _ in range(m):
    x, y = map(int, input().split())
    adj[y].append(x)
 
 
def bfs(v):
    q = deque([v])
    visited = [False] * (n + 1)
    visited[v] = True
    count = 1
    while q:
        v = q.popleft()
        for e in adj[v]:
            if not visited[e]:
                q.append(e)
                visited[e] = True
                count += 1
    return count
 
result = []
max_value = -1
 
for i in range(1, n + 1):
    c = bfs(i)
    if c > max_value:
        result = [i]
        max_value = c
    elif c == max_value:
        result.append(i)
        max_value = c
 
for e in result:
    print(e, end=" ")