이코테 Chapter 09 최단경로 - 미래 도시

문제

방문 판매원 A는 많은 회사가 모여 있는 공중 미래 도시에 있다. 공중 미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다. 방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하려 한다. 공중 미래 도시에서 특정 회사에 도착하기 위한 방법은 회사끼리 연결되어 있는 도로를 이용하는 방법이 유일하다. 또한 연결된 2개의 회사는 양방향으로 이동할 수 있다. 이 때, 다른회사로 이동하기 위한 시간은 정확히 1만큼의 시간이 소요된다.

 

또한 오늘 A씨는 소개팅에도 참여해야 한다. 소개팅의 상대는 K번 회사에 존재한다. 방문 판매원 A는 X번 회사에 물건을 팔러 가기 이전에 소개팅 상대의 회사에 가서 함께 커피를 마실 예정이다. 따라서 A씨는 1번 회사에서 출발해 K번 회사를 거쳐 X번 회사로 가는 것이 목표다. 이 때 A씨는 가장 빠르게 이동하려고 한다. A씨가 이동하게 되는 최소 시간을 계산하는 프로그램을 작성해라. 이 때 소개팅의 상대방과 커피를 마시는 시간 등은 고려하지 않는다.

 

입력조건

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

출력조건

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

 

접근법

1. 판매원 A가 K에 거쳐 X로 가는 최단 시간을 구하는 거니깐 1에서 K로 가는 최단 시간을 구하고 K에서 X로가는 최단시간을 더하면 될거같았다.

 

[소스 코드]

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

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


for _ in range(m):
  a, b = map(int, input().split())
  graph[a].append((b, 1))
  graph[b].append((a, 1))

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


# 현재 노드에서 가장 거리가 짧은 노드의 인덱스를 반환하는 함수
def get_smallest_node():
  min_value = INF
  index = 0
  for i in range(1, n + 1):
    if distance[i] < min_value and not visited[i]:
      min_value = distance[i]
      index = i
  return index
  
def dijkstra(start, end):
  
  distance[start] = 0
  visited[start] = True

  for node, dist in graph[start]:
    distance[node] = dist

  for i in range(n - 1):
    now = get_smallest_node()
    visited[now] = True
    for node, dist in graph[now]:
      cost = distance[now] + dist
      if cost < distance[node]:
        distance[node] = cost

  return distance[end]
  
distance_k= dijkstra(1, k)

distance = [INF] * (n + 1)
visited = [False] * (n + 1)

distance_x = dijkstra(k, x)

for i in range(1, n + 1):
  print(distance[i])
  
if distance_k == INF or distance_x == INF:
  print(-1)
else:
  print(distance_k + distance_x)

근데 코딩하고 보니깐 책에 나와있는 테스트케이스에서는 정상적으로 출력하긴하는데 반례가 있을 거같아서 정확한지를 모르겠다..

 

오답노트 & 알아낸 것

- 일단 n의 범위가 1 ~ 100 사이여서 힙을 이용하지는 않고 기본적인 다익스트라 알고리즘을 사용하였는데 이런 경우에는 다익스트라 알고리즘말고 플로이드워셜 알고리즘을 쓰는것이 훨씬 간편할 것 같다고 느꼈다. 최단 경로 문제를 만나면 앞으로는 어떤 알고리즘이 가장 잘 어울릴지 더 생각을 하고 풀어야겠다.
- 양방향 그래프일 경우 양방향의 값을 잘 설정해줘야겠다. 처음에 결과가 이상하게 나오길래 뭐지 싶었는데 양방향 값을 설정안했더라,,