<aside> 🔥 이코테 문제

</aside>

<aside> 🔥 문제 정리

첫줄에 입력값 n : 노드의 개수, m : 간선의 개수가 주어진다.

m개에 줄에 각 노드가 연결된 간선이 주어진다.

마지막줄에 x : 목적지, k : 경유지가 주어진다.

모든 노드에서 노드로 가는 시간은 1이며, 1번 노드에서 시작해 경유지 k를 거쳐 목적지 x로 가는데

시간을 출력하라.

</aside>

<aside> 🔥 이 문제는 플로이드 워셜 알고리즘으로 풀 수있다고한다.

<aside> 🔥 플로이드 워셜 알고리즘이란?

다익스트라 알고리즘과 같은 원리로 단계마다 거쳐가는 노드를 기준으로 알고리즘을 수행한다.

하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다.

2차원 리스트에 최단 거리 정보를 담아야 한다.

전체적으로 3중 반복문을 이용하여 아래 점화식에 따라 최단 거리 테이블을 갱신한다.

Dab = min(Dab, Dak + Dkb)

따라서 시간 복잡도는 O(N^3)이다.

</aside>

</aside>

<aside> 🔥 코드 진행

1. n, m ( 노드 개수, 간선 개수)를 입력받고 그래프를 무한으로 초기화한다.

   # 노드의 개수 및 간선의 개수를 입력받기
   n, m = map(int, input().split())
   # 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
   graph = [[INF] * (n + 1) for _ in range(n + 1)]
   

2. 자기 자신에서 자기 자신으로 가는 비용은 없으므로 0으로 설정해준다.

   

   # 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
   for a in range(1, n + 1):
       for b in range(1, n + 1):
           if a == b:
               graph[a][b] = 0
   

3. 각 간선에 대한 시간 정보를 입력받아 그 값으로 초기화 해준다.

   여기서 모든 비용은 1이라 1로 설정.

   

   for _ in range(m):
       # A와 B가 서로에게 가는 비용은 1이라고 설정
       a, b = map(int, input().split())
       graph[a][b] = 1
       graph[b][a] = 1
   

4. 경유지와 최종 목적지를 입력받고

   점화식에 따라 플로이드 워셜 알고리즘을 실행해준다.

   

   # 거쳐 갈 노드 X와 최종 목적지 노드 K를 입력받기
   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])
   

5. 결과 출력

   # 수행된 결과를 출력
   distance = graph[1][k] + graph[k][x]
   
   # 도달할 수 없는 경우, -1을 출력
   if distance >= 1e9:
       print("-1")
   # 도달할 수 있다면, 최단 거리를 출력
   else:
       print(distance)
   

</aside>