[이코테] 최단경로 - 미래 도시

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

방문 판매원 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번이라고 주어져서 "특정 노드에서 다른 노드들까지의 거리"를 측정하는 마인드 하에 다익스트라 알고리즘을 구현하려 했다. 그런데 중간에 K번 노드를 거쳐야 하는 이슈를 고려하지 못했다. 그래서 좀 더 사고를 확장해서 "시작노드 -> K번 노드의 최단거리 + K번 노드 -> X번 노드의 최단거리"가 시작노드 -> K -> X로 가는 최단거리가 아닐까? 생각함. 결국 모든 노드에서 모든 노드까지의 거리를 측정하는 플로이드 워셜 알고리즘을 사용
• 또한 주어진 범위 조건이 100이하 값이므로 3중 반복문을 사용하는 플로이드 워셜로 구현이 가능하다고 생각함.
• 문제 조건에서 양방향이라는 것을 보고 2차원 거리 테이블을 업데이트 할 때 행, 열을 바꾼 값도 동일하겠다고 생각함.
• 간선 비용이 모두 1이라는 점도 염두에 두고 품(이것은 문제 풀이를 크게 변화시키지는 않음)

풀이

1. 나의 풀이

import sys

n, m = map(int, input().split())
INF = int(1e9)
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, 비용은 1
    a, b = map(int, input().split())
    graph[a][b] = 1
# 1번 -> K -> X로 가는 최단경로
x, k = map(int, input().split())
start = 1

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])
            graph[b][a] = graph[a][b]  # 양방향이므로 행,열 바꾼 값도 동일함

if graph[start][k] == INF or graph[k][x] == INF:
    print(-1)
else:
    res = graph[start][k] + graph[k][x]
    print(res)

2. 책의 풀이

책에서는 그래프 데이터 정보를 입력받을 때, 양방향 조건을 만족시키게 했다. 그리고 시작노드 -> K -> X 거리를 마지막 조건문 이전에 미리 구하고 if 문을 작성함

 

import sys

n, m = map(int, input().split())
INF = int(1e9)
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 # 내 풀이와 다른 점

# 1번 -> K -> X로 가는 최단경로
x, k = map(int, input().split())
start = 1

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[start][k] + graph[k][x]
if distance >= INF:
    print(-1)
else:
    print(distance)