We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
간선 가중치가 1이기 때문에 BFS로 더 빠르게 풀이할 수 있을 것 같습니다. 이 경우 큐에 넣고 빼기 위한 연산이 최대 간선의 개수만큼 반복되므로 시간 복잡도는 O(E)=O(V^2)입니다. 이 풀이도 적절한가요??
from collections import deque def get_distance(graph, start, destination): """ BFS로 최단 거리 구하기 """ queue = deque([(start, 0)]) visited = set() while queue: here, distance = queue.popleft() if here == destination: return distance if here not in visited: visited.add(here) for next in graph[here]: queue.append((next, distance + 1)) return -1 # 입력 n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] for _ in range(m): node1, node2 = map(int, input().split()) graph[node1].append(node2) graph[node2].append(node1) x, k = map(int, input().split()) # 출력 meetting_distance = get_distance(graph, 1, k) if meetting_distance > -1: dating_distance = get_distance(graph, 1, x) if dating_distance > -1: print(meetting_distance + dating_distance) else: print(-1) else: print(-1)
The text was updated successfully, but these errors were encountered:
No branches or pull requests
간선 가중치가 1이기 때문에 BFS로 더 빠르게 풀이할 수 있을 것 같습니다.
이 경우 큐에 넣고 빼기 위한 연산이 최대 간선의 개수만큼 반복되므로 시간 복잡도는 O(E)=O(V^2)입니다.
이 풀이도 적절한가요??
The text was updated successfully, but these errors were encountered: