[BOJ] #1325 - 효율적인 해킹

1325번: 효율적인 해킹

 

 

** 문제 유형

• DFS, BFS

 

** 풀이

1. 모든 정접에 대하여 DFS or BFS를 수행
   • 처리해야 하는 데이터 수가 많을 경우, BFS를 수행하는 것이 유리
2. DFS or BFS를 수행할 때마다 방문하게 되는 노드의 개수 계산
3. 노드의 개수가 가장 크게 되는 시작 정점을 출력

 

from collections import deque

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

---

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)

result = []
max_value = -1

for i in range(1, n + 1):
    c = bfs(i) # 모든 정점에 대해 bfs 수행

    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=" ")