[CodingTest] 미래도시 ( 플로이드-워셜 알고리즘 )

 

◎ 문제

공중미래도시는 1번부터 N번까지 회사가 있으며 서로 도로로 연결되어 있다. 방문판매원A는 현재 1번에 있으며 X번 회사에 방문하여 물건을 판매하려고 한다. 연결된 2개의 회사는 양방향 이동이 가능하다. 회사와 회사를 연결하는 도로는 마하의 속도로 사람을 이동시켜 모두 정확히 1만큼의 시간으로 이동한다. 또한 방문판매원A는 소개팅에도 참석하려고 한다. 소캐팅 상대는 K번회사에 있다. 방문판매원A는 K번회사에 참석한 뒤 X번 회사로 가는 것이 목표다. 방문판매원이 회사 사이를 이동하는 최소시간을 계산하는 프로그램을 작성하시오. 

 

- 입력조건

• 첫째 줄에 전체 회사의 개수 N과 경로의 개수 M이 공백으로 구분되어 차례대로 주어진다.(1 <= N, M <= 100)
• 둘째 줄부터 M+1 번째 줄에는 연결된 두 회사의 번호가 공백으로 구분되어 주어진다.
• M+2 번째 줄에는 X와 K가 공백으로 구분되어 차례대로 주어진다.(1 <= K <= 100)

 

- 출력조건

• 첫째 줄에 방문 판매원 A씨가 K번 회사를 거쳐 X번 회사로 가는 최소 이동 시간을 출력한다.
• 만약 X번 회사에 도달할 수 없다면 -1을 출력한다.

 

◎ 알고리즘

처음에 출발지점이 1로 고정되어 있어 다익스트라 알고리즘을 떠올렸다. 문제 후반부에 K번 회사를 경유한다는 말을 듣고 플로이드-워셜 알고리즘으로 바꾸었다.

 

출발지점 : 1

경유지점 : K

도착지점 : X

 

다익스트라 알고리즘은 1 ➞ K, 1 ➞ X로 가는 최단경로는 구할수 있지만 K ➞ X로 가는 최단경로는 구하지 못한다. 문제가 요구하는 바는 [ 1 ➞ K 최단경로 + K ➞ X 최단경로 ] 이다. 모든노드에서 모든노드로 가는 최단경로는 플로이드-워셜 알고리즘을 사용하면 구할 수 있다.

 

◎ 코드구현

INF = int(1e9)
n,m = map(int, input().split())

graph = [ [INF]*(n+1) for _ in range(n+1)]

#그래프 간선 초기화
for _ in range(m) :
  com1, com2 = map(int,input().split())
  graph[com1][com2] = 1 #양방향 간선 
  graph[com2][com1] = 1 #양방향 간선 

x,k = map(int,input().split())


#D(1,K) 최단경로 + D(K,X) 최단경로 
for middle in range(1,n+1) :
  for start in range(1,n+1) :
    for end in range(1,n+1) :
      graph[start][end] = min(graph[start][end], graph[start][middle]+graph[middle][end])

result = graph[1][k] + graph[k][x] #D(1,K) 최단경로 + D(K,X) 최단경로 

#출력
if result >= INF : print(-1)
else : print(result)

 

 

---

 

참고자료

이것이 취업을 위한 코딩 테스트다 with 파이썬 : 네이버 도서