이번 문제는 작년 카카오 기출인 Lv.3 합승 택시 요금입니다.
작년 카카오 공채 컷이 3솔 정도라고 하던데 이 문제가 4번 문제니까 어려운 문제 중 하나였나 봅니다. (오히려 저는 3번은 못풀고 이건 생각을 어떻게 해내긴 했습니다)
여튼 문제는 그래프로 주어진 정점 간 요금 정보가 주어집니다. 여기서 시작점으로부터 A와 B의 집으로 가는 최저 요금을 구하는 데, 어디까지 합승해야 최저 요금일지를 계산하는 문제입니다.
처음에는 BFS로 모두 탐색을 해볼까했는데 쉽지 않을 것 같아 한번 모든 정점을 합승 지점으로 생각해볼까? 하는 생각이 들었습니다. (맨 처음 볼 땐 생각못했는데 저번에 시간 복잡도는 일단 생각하지말고 방법부터 생각하는 식으로 접근하다보니 생각났습니다)
시작 지점을 포함해 모든 지점을 합승 지점으로 생각하고, 그 지점에서 각자의 집으로 돌아가는 최단 거리를 더한 것을 비교하여 최솟값을 찾으면 되겠다 싶었습니다.
처음에는 다익스트라 알고리즘을 이용해야되나 싶었는데 이것은 시작점과 종점이 정해진 케이스만 있으므로 매우 귀찮을 것 같아서 dp식으로 최단거리를 계산하는 플로이드 와샬 알고리즘을 사용했습니다.
먼저 시작 정점으로부터 도착 정점까지 거리를 저장할 배열을 선언하고 주어진 자료를 입력받습니다.
answer = sys.maxsize
# 모든 노드 간 거리 배열 생성
distance = [[sys.maxsize for _ in range(n+1)] for _ in range(n+1)]
# 연결된 노드 정보 입력
for p1, p2, fare in fares:
distance[p1][p2] = fare
distance[p2][p1] = fare
for i in range(n+1):
distance[i][i] = 0그 다음으로 모든 정점 간 최단 거리를 구하기 위해 플로이드-와샬 알고리즘을 사용합니다.
간단히 플로이드 와샬 알고리즘을 설명하자면, i번 정점으로부터 j번 정점까지 가는데 임의의 경유 정점을 하나씩 정하는 것입니다. 그러다 만약 경유를 한 것이 i부터 j까지 바로 간 경로보다 짧으면, 그 때 i에서 j로 가는 거리를 갱신해줍니다.
즉, 모든 노드 간 연결 상태를 검사할 때 모든 노드를 한번씩 거쳐가는 거리로 조사하는 셈입니다.
코드는 의외로 간단하며, 다음과 같습니다.
# 플로이드-와샬 알고리즘을 통해 모든 정점 간 최단거리 구하기
for inter in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
if (distance[i][inter] + distance[inter][j]) < distance[i][j]:
distance[i][j] = distance[i][inter] + distance[inter][j]i는 출발 정점, j는 도착 정점, inter는 중간에 경유하는 정점을 의미합니다.
이렇게 모든 정점 간 최단 거리를 구했으니, 모든 합승케이스를 조사해봅니다.
# 한 정점씩 합승 지점을 정한다.
# 합승 지점까지의 최단거리 + 그 지점에서부터 (a의 집 거리 + b의 집거리)
for i, dist in enumerate(distance[s]):
answer = min(answer, dist + distance[i][a] + distance[i][b])
return answer모든 정점을 합승 지점으로 가정한 다음, (합승 지점까지 가는 최단 거리) + (합승 지점으로부터 내려서 각자 집으로 가는 최단거리)를 더한 것 중 가장 작은 값을 구해주면 통과가 됩니다.
다행히 효율성 테스트까지 통과할 수 있었습니다. 정점 개수가 200개가 최대였기 때문에 시간 복잡도는 조금 내려놓고 일단 어떻게 풀지부터 고민한게 효과적이었다고 봅니다. 역시, 일단 풀고나서 개선하자가 맞을진 모르지만 빠르게 풀기엔 효과적인 것 같습니다.
시간 복잡도 : O(n^3) , n : 노드의 개수
플로이드-와샬 알고리즘 계산 시 n^3의 계산을 수행한다
