[python] 백준 - 1325. 효율적인 해킹

🤔문제 해결

• S2 | 그래프, BFS(DFS)

단순한 그래프 문제였는데 전부다 시간초과 발생....

다른 분들 제출한것도 보니까 대부분 시간초과이다. (그래서 pypy3로 제출하니 성공)

 

풀이방법은

1. 인접리스트 생성 (이 문제에서는 a->b가 아니라 b->a 이다)
2. 모든 노드에 대해서
3. BFS를 돌린다. 그 때 몇개의 노드를 돌았는지 숫자를 세준다.
4. 가장 높은 카운트의 노드들을 출력한다.

다른 분들의 풀이를 봤는데 풀이가 나랑똑같다. 하지만 어떻게 통과했는지...

 

💻소스 코드

import sys
from collections import defaultdict
from collections import deque


def bfs(start):
    q = deque([start])
    visited = [0] * (N + 1)
    visited[start] = 1
    cnt = 0
    while q:
        c = q.popleft()
        cnt += 1
        for nei in adj[c]:
            if not visited[nei]:
                q.append(nei)
                visited[nei] = 1

    return cnt


input = sys.stdin.readline

N, M = map(int, input().split())

adj = defaultdict(list)
for _ in range(M):
    e, s = map(int, input().split())
    adj[s].append(e)

print(adj)

result = []
for i in range(1, N + 1):
    result.append([bfs(i), i])

print(result)

result.sort(key=lambda x: (-x[0], x[1]))

max_cnt = result[0][0]
for r in result:
    if r[0] == max_cnt:
        print(r[1], end=" ")
    else:
        break

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

1325번: 효율적인 해킹