문제 보기 · Level 3 · 2021 KAKAO BLIND RECRUITMENT · 정답률 43% · 푼 사람 13,289명 (2026-09-30 기준)1

문제

지점 n개와 지점 사이 택시 요금(양방향)이 주어진다. A와 B가 s에서 함께 출발해 각자 a, b로 간다. 어느 지점까지 합승하고 거기서 따로 가도 되고, 처음부터 따로 가도 된다. 두 사람 요금 합의 최솟값을 돌려준다.

  • 3 ≤ n ≤ 200, s, a, b는 서로 다르다
  • 요금 1 ~ 100,000, 두 지점 사이 요금은 하나만 주어진다
  • s에서 a, b로 가는 길은 늘 있다

풀이

막히면 한 단계씩 펼친다.

필요한 개념

플로이드–워셜: 갈라지는 지점 k를 모두 해 보려면 s → k, k → a, k → b의 최단 요금이 필요하다. 지점이 200개 이하라 모든 쌍의 최단 요금표를 한 번에 만든다.

1단계 · 작은 예로 손으로 풀기

합승은 이런 모양이다: s에서 k까지 함께 타고(요금 한 번), k에서 A는 a로, B는 b로 따로 간다. 그래서 요금 합은

(s → k 요금) + (k → a 요금) + (k → b 요금)

이다. k = s면 처음부터 따로 가는 것이다. 모든 k 중 가장 작은 값이 답이다. 각 부분은 당연히 최단 요금으로 가야 한다.

예시 1에서 k = 5면 s(4) → 1 → 5가 34원, 5 → 6이 2원, 5 → 3 → 2가 46원으로 합이 82원이다.

2단계 · 가장 단순한 방법과 그 속도

A의 길과 B의 길을 모두 짝지어 보면 길의 수가 폭발한다. 1단계처럼 “갈라지는 지점 k”만 고르면 k는 200가지뿐이다. 필요한 것은 최단 요금 세 가지를 빨리 아는 것이다.

3단계 · 핵심 아이디어
  • 모든 쌍의 최단 요금표: 플로이드–워셜로 D[i][j]를 한 번 만든다. n = 200이면 800만 번이다.
  • 갈라지는 지점을 모두 해 보기: 답은 모든 k에 대한 D[s][k] + D[k][a] + D[k][b]의 최솟값이다. 요금이 양방향이라 D[k][a] = D[a][k]다.
  • 다른 방법: s, a, b에서 다익스트라를 한 번씩 돌려도 같은 세 값을 얻는다. 요금이 양방향이라 “k에서 a까지”는 “a에서 k까지”와 같기 때문이다. 점과 간선이 많을 때는 이쪽이 빠르다.
4단계 · 코드 흐름
  1. (n + 1)×(n + 1) 표를 무한대로 채우고 D[i][i] = 0, 요금을 양쪽에 적는다.
  2. 플로이드–워셜을 돌린다.
  3. k = 1 ~ n에서 D[s][k] + D[k][a] + D[k][b]의 최솟값을 돌려준다.
5단계 · 파이썬 코드 
def solution(n, s, a, b, fares):
    INF = float("inf")
    D = [[INF] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        D[i][i] = 0
    for c, d, f in fares:
        D[c][d] = D[d][c] = f                   # 양방향
    for k in range(1, n + 1):                   # 거쳐 가도 되는 지점을 늘린다
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if D[i][k] + D[k][j] < D[i][j]:
                    D[i][j] = D[i][k] + D[k][j]
    return min(D[s][k] + D[k][a] + D[k][b] for k in range(1, n + 1))
  • D[c][d] = D[d][c] = f: 두 칸에 같은 값을 한 줄로 넣는다.
  • 효율성 테스트가 빠듯하면 안쪽 반복 전에 D[i][k]가 무한대인 i를 건너뛰고, D[i], D[k]를 변수에 잡아 두면 빨라진다. 검증 코드의 풀이가 그렇게 짜여 있다.
6단계 · 실행 추적

예시 1: n = 6, s = 4, a = 6, b = 2. 플로이드–워셜을 끝낸 표에서 갈라지는 지점마다 더한다.

갈라지는 지점 k D[4][k] D[k][6] D[k][2] 합
1 10 25 63 98
2 66 48 0 114
3 51 26 22 99
4 (합승 안 함) 0 35 66 101
5 34 2 46 82
6 35 0 48 83

5에서 갈라질 때 82원으로 가장 싸다. 합승하지 않으면 101원이다.

7단계 · 복잡도와 흔한 실수

플로이드–워셜 \(O(n^3)\), 갈라지는 지점 고르기 \(O(n)\)이다. n = 200, 모든 쌍에 요금이 있는 입력으로 재 보니 0.2초가 안 걸렸다.

  • k = s(합승 안 함)를 빼먹는다. 범위를 1 ~ n 전체로 돌리면 저절로 들어간다.
  • 요금을 한쪽 방향에만 적는다.
  • 플로이드–워셜의 반복 순서를 바꿔 k를 안쪽에 둔다.
검증: 문제의 예시 3개를 통과했다. 무작위 그래프 800개(지점 6개 이하)에서 “s, a, b에서 다익스트라를 돌리는” 풀이, “s → a 경로와 s → b 경로를 모두 짝지어 앞부분이 같은 동안 함께 탄다고 세는” 풀이와 결과가 모두 같았다. 6단계 표의 값과 큰 입력의 시간도 확인했다 — 27_pg72413_p1.py

  1. 프로그래머스 스쿨, “합승 택시 요금” (https://school.programmers.co.kr/learn/courses/30/lessons/72413), 2026-09-30 조회. ↩