[Algorithm] 미래도시
INF = int(1e9)
n, m = map(int, input().split())
graph = [[INF] * (n + 1) for _ in range(n + 1)]
# 자기 방향 제외
for a in range(1, n + 1):
for b in range(1, n + 1):
if a == b:
graph[a][b] = 0
# 양방향
for _ in range(m):
a, b = map(int, input().split())
graph[a][b] = 1
graph[b][a] = 1
x, k = map(int, input().split())
for k in range(1, n + 1):
for a in range(1, n + 1):
for b in range(1, n + 1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
distance = graph[1][k] + graph[k][x]
if distance >= INF:
print("-1")
else:
print(distance)
1번 노드에서 5번 노드를 거쳐 4번노드로 가는 문제이다.
문제만 보면 다익스트라 플로이드나 아무렇게 풀어도 상관없지만 시간복잡도가 널널하기 때문에 더 구현하기 쉬운 플로이드 워셜 알고리즘을 이용해서 구현했다.
거리 그래프를 만드는데 자기자신으로 가는것과 1-2(1->2 2->1) 양방향으로 움직일수있다는점을 고려해 그래프를 만든다.
시작 노드 목표 노드 중간 노드가 모두 고려되는 3차원 for문을 만들고
distance는 무조건 중간노드를 거쳐야하기 때문에
distance = graph[1][k] + graph[k][x] 설정한다.
Author And Source
이 문제에 관하여([Algorithm] 미래도시), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jifrozen/Algorithm-미래도시저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)