Skip to content

Instantly share code, notes, and snippets.

@jsrimr
Created March 14, 2022 11:10
Show Gist options
  • Save jsrimr/68ae83104702e889c24399749040762a to your computer and use it in GitHub Desktop.
Save jsrimr/68ae83104702e889c24399749040762a to your computer and use it in GitHub Desktop.
각 노드마다 bfs 적용함
from collections import defaultdict, deque
def solution(edges):
graph = defaultdict(list)
for (n1, n2) in edges:
graph[n1].append(n2)
graph[n2].append(n1)
answer = 0
def bfs(start):
nonlocal answer
queue = deque([(start, 0)])
visited = set()
while queue:
n, path_len = queue.popleft()
if path_len > 1:
answer += (path_len-1)
for other in graph[n]:
if other not in visited:
queue.append((other, path_len+1))
visited.add(n)
for n in graph:
bfs(n)
return answer
if __name__ == '__main__':
edges = [[0,1],[0,2],[1,3],[1,4]]
edges = [[2,3],[0,1],[1,2]]
print(solution(edges))
@jsrimr
Copy link
Author

jsrimr commented Mar 14, 2022

다만 이렇게 하면 O(N*(N+logN)) 시간복잡도가 되어 시간초과가 날 것 같음

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment