BOJ 백준 1325번 효율적인 해킹 | Python
🔎 문제 설명
🩶 실버 1
- 난이도 ★★☆☆
- 그래프탐색 BFS
기본적인 그래프탐색을 구현만 할 수 있다면 쉽게 풀 수 있는 문제다! 그러나 시간초과가 항상 문제가 되는…
나는 BFS/DFS로 구현을 해서 해결했으나, Python3로는 계속 시간초과가 떠서 Pypy3로 제출해서 성공했다. 다른 방법이 있나 더 찾아봐야겠다.
📌 문제 풀이 큰 틀은 다음과 같다.
- A가 B를 신뢰한다 = B를 해킹하면 A도 해킹이 된다!
- 그래프 탐색으로 해결
💻 내 코드
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
computers = [[] for _ in range(N+1)]
for _ in range(M):
a, b = map(int, input().split())
computers[b].append(a)
answer = 0
ans_lst = []
def bfs(node):
visited = [0 for _ in range(N+1)]
queue = deque([node])
visited[node] = 1
cnt = 1
while queue:
now = queue.popleft()
for n in computers[now]:
if not visited[n]:
visited[n] = 1
queue.append(n)
cnt += 1
return cnt
for i in range(1, N+1):
if len(computers[i]) > 0:
tmp = bfs(i)
if answer < tmp:
answer = tmp
ans_lst=[i]
elif answer == tmp:
ans_lst.append(i)
print(*ans_lst)
💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).