문제 보기 · Level 4 · 2017 카카오코드 본선 · 정답률 8% · 푼 사람 318명 (2026-09-30 기준)1

문제

m×n 파티장의 왼쪽 위 (0, 0)에서 오른쪽 아래 (m − 1, n − 1)까지 상하좌우로 한 칸씩 간다. 칸마다 그 칸 친구와 나눌 대화 시간이 적혀 있고, −1인 칸은 테이블이라 못 지나간다. 시작 칸과 도착 칸의 대화 시간은 0이다.

대화 시간 합이 s를 넘는 길은 쓸 수 없다. 쓸 수 있는 길 가운데 가장 짧은 길을 고르고, 길이가 같으면 대화 시간 합이 적은 길을 고른다. [길의 걸음 수, 대화 시간 합]을 돌려준다.

  • 2 ≤ m, n ≤ 50
  • 1 ≤ s ≤ \(2^{31}-1\), 대화 시간은 −1 ~ \(2^{31}-1\)
  • 조건에 맞는 길이 늘 하나 이상 있다

풀이

막히면 한 단계씩 펼친다. 칸은 (행, 열)로 적고 0부터 센다.

필요한 개념

동적 계획법: “정확히 k걸음에 이 칸에 왔을 때의 최소 대화 시간”을 걸음 수 순서로 채운다. 한 층씩 넓혀 가는 모양은 너비 우선 탐색과 같다. 다만 칸마다 한 번만 들르지 않는다.

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

문제의 세 번째 예시 판이다. s = 12다.

0 1 1 1 1
9 9 9 1 9
1 1 1 1 9
1 1 5 9 9
1 1 1 1 0
  • 가장 짧은 길은 8걸음이다. 하지만 8걸음 길은 어떻게 가도 9나 5를 밟아, 대화 시간이 가장 적은 길도 15다. 12를 넘으니 못 쓴다.
  • 10걸음 길은 가장 적어도 13이라 역시 못 쓴다.
  • 12걸음에 11인 길이 있다. 오른쪽 3칸 → 아래 2칸 → 왼쪽 2칸 → 아래 2칸 → 오른쪽 3칸으로 1만 밟는다. 답은 [12, 11]이다.

같은 판에서 s만 바꾸면 답이 이렇게 바뀐다.

s 11 ~ 12 13 ~ 14 15 이상
답 [12, 11] [10, 13] [8, 15]

s가 빠듯할수록 멀리 돌아간다. 걸음 수와 대화 시간을 함께 따져야 한다.

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

같은 칸을 두 번 밟지 않는 길을 모두 만들고(백트래킹), 대화 시간이 s 이하인 길 가운데 (걸음, 대화 시간)이 가장 작은 것을 고른다. 답은 맞지만 길의 수가 너무 많다. 벽 없는 빈 판의 길 수를 세어 보면 4×4에 184개, 5×5에 8,512개, 6×6에 1,262,816개다. 한 변이 1 늘 때마다 수십~백 배 넘게 는다. 50×50은 어림없다.

3단계 · 핵심 아이디어
  • 걸음 수로 층을 나눈다: k걸음에 닿는 칸들을 한 층으로 본다. 칸마다 “정확히 k걸음에 왔을 때의 최소 대화 시간”을 적는다. 다음 층의 값은 이웃 칸의 값에 그 칸의 대화 시간을 더한 것 중 가장 작은 값이다.
  • 도착 칸이 처음 나온 층이 답이다: 층을 0, 1, 2, …로 늘리다 도착 칸이 처음 나오면, 그 k가 가장 짧은 길이다. 그 층에 적힌 값이 그 길이의 최소 대화 시간이다. 대화 시간은 0 이상이라 한 번 s를 넘은 길은 다시 내려오지 않는다. 그래서 s를 넘는 값은 바로 버린다.
  • 같은 칸에 다시 와도 된다: 이 표는 왔던 칸을 다시 밟는 길도 센다. 그래도 답은 안 바뀐다. 길에 고리가 있으면 고리를 빼도 걸음은 줄고 대화 시간은 늘지 않는다. 그러니 가장 짧은 답 길에는 고리가 없다. 칸을 다시 밟아도 되는 길을 보행(walk), 다시 밟지 않는 길을 경로(path)라 한다. 이 논리는 경로와 연결성의 “가장 짧은 보행은 경로다”를 대화 시간까지 따지도록 넓힌 것이다.
  • 버려도 되는 상태: 어떤 칸에 더 적은 걸음으로, 같거나 적은 대화 시간으로 온 적이 있으면 지금 상태는 버린다. 지금 상태로 갈 수 있는 곳은 그 전 상태가 더 빨리, 더 싸게 갈 수 있다. 그래서 best[칸]에 앞 층들의 최소 대화 시간을 적어 두고, 이보다 작을 때만 층에 넣는다. (걸음, 대화 시간) 쌍을 “둘 다 같거나 작다”로 비교하면 부분순서가 된다. 6단계에서 칸 (2, 2)에 온 (4걸음, 12)와 (6걸음, 6)은 어느 쪽도 다른 쪽보다 작지 않아 둘 다 남는다. 칸마다 남는 상태는 이 순서의 극소 원소(자기보다 작은 것이 없는 원소)다.
4단계 · 코드 흐름
  1. best를 모두 무한대로 두고 best[0][0] = 0. 첫 층은 {(0, 0): 0}, k = 0.
  2. 층이 비지 않는 동안 되풀이한다. 도착 칸이 층에 있으면 [k, 그 값]을 돌려준다.
  3. 층의 칸마다 네 방향 이웃을 본다. 판 밖이나 −1이면 건너뛴다. t = 지금 값 + 이웃의 대화 시간.
  4. t ≤ s이고, t < best[이웃]이고, 다음 층에 적힌 값보다 작을 때만 다음 층에 넣는다.
  5. 층을 다 보면 다음 층의 값으로 best를 고치고, 다음 층으로 넘어가 k를 1 늘린다.
5단계 · 파이썬 코드 
DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))

def solution(m, n, s, time_map):
    INF = float("inf")
    best = [[INF] * n for _ in range(m)]   # 앞 층들에서 그 칸에 온 최소 대화 시간
    best[0][0] = 0
    layer = {(0, 0): 0}                    # 정확히 k걸음에 온 칸 → 최소 대화 시간
    k = 0
    while layer:
        if (m - 1, n - 1) in layer:
            return [k, layer[(m - 1, n - 1)]]
        nxt = {}
        for (r, c), talk in layer.items():
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and time_map[nr][nc] != -1:
                    t = talk + time_map[nr][nc]
                    if t <= s and t < best[nr][nc] and t < nxt.get((nr, nc), INF):
                        nxt[(nr, nc)] = t
        for (r, c), t in nxt.items():
            best[r][c] = min(best[r][c], t)
        layer = nxt
        k += 1
    return [-1, -1]
  • layer를 딕셔너리로 둔다: 같은 층에서 한 칸에 여러 길로 오면 가장 작은 값 하나만 남는다.
  • t < best[nr][nc]: 앞 층에서 같거나 더 싸게 온 적이 있으면 버린다. 시작 칸은 best가 0이라 다시 들어가지 않는다.
  • nxt.get((nr, nc), INF): 아직 다음 층에 없는 칸이면 무한대를 꺼내 비교한다.
6단계 · 실행 추적

1단계의 판(s = 12)에서 층마다 남는 칸과 대화 시간이다.

k 층에 남은 칸 (대화 시간)
0 (0, 0) 0
1 (0, 1) 1, (1, 0) 9
2 (0, 2) 2, (1, 1) 10, (2, 0) 10
3 (0, 3) 3, (1, 2) 11, (2, 1) 11, (3, 0) 11
4 (0, 4) 4, (1, 3) 4, (2, 2) 12, (3, 1) 12, (4, 0) 12
5 (2, 3) 5
6 (2, 2) 6
7 (2, 1) 7, (3, 2) 11
8 (2, 0) 8, (3, 1) 8, (4, 2) 12
9 (3, 0) 9, (4, 1) 9
10 (4, 0) 10, (4, 2) 10
11 (4, 3) 11
12 (4, 4) 11
  • k = 5: 12인 칸들은 어디로 가도 12를 넘는다. (0, 4)와 (1, 3)에서 (1, 4)로 가면 13이라 버린다. (1, 3) → (2, 3)의 5만 남는다.
  • k = 6: (2, 2)가 다시 나온다. 4걸음에 12로 왔던 칸인데, 6걸음에 6으로 오니 더 싸서 남긴다. 이 6짜리가 답 길을 이어 간다.
  • k = 10: (4, 2)도 8걸음 12에서 10걸음 10으로 다시 들어간다.
  • k = 12: 도착 칸이 처음 나온다. 답은 [12, 11]이다.
7단계 · 복잡도와 흔한 실수

층마다 칸은 많아야 mn개다. 층은 많아야 mn개다. mn걸음 이상인 길에는 고리가 생기고, 고리를 뺀 더 짧은 길이 같거나 적은 대화 시간으로 이미 와 있어 버려지기 때문이다. mn걸음을 걸으면 시작 칸을 포함해 mn + 1번 칸을 밟는데 칸은 많아야 mn개라, 비둘기집 원리로 어떤 칸은 두 번 밟는다. 그래서 최악은 \(O((mn)^2)\)이다. 실제로는 칸이 대화 시간이 줄 때만 층에 다시 들어가 훨씬 적다. 50×50 판 23개(값이 \(2^{31}-1\)까지인 판, 벽이 30%인 판, 1,274걸음을 돌아가는 판 포함)를 모두 풀어도 0.01초쯤 걸렸다.

  • 칸마다 한 번만 들르는 너비 우선 탐색을 쓴다. 1단계 판에서 (2, 2)에 4걸음 12로 먼저 와서 칸을 막아 버린다. 6걸음 6으로 오는 길이 막혀 도착 칸에 못 간다.
  • 대화 시간만 줄이는 다익스트라를 쓴다. 1단계 판에서 s = 100이면 답은 [8, 15]다. 그런데 대화 시간이 가장 적은 길은 12걸음에 11이다. 걸음 수가 먼저다.
  • [대화 시간, 걸음 수] 순서로 돌려준다. 순서는 [걸음 수, 대화 시간]이다.
  • C++이나 자바로 옮기면 대화 시간 합이 int 범위를 넘을 수 있다. 파이썬 정수는 크기 제한이 없다.
검증: 문제의 예시 3개, 1단계의 s별 답, 6단계 표의 층 값을 코드로 확인했다. 무작위 판 800개(4×4 이하)에서 “겹치지 않는 길을 모두 만드는” 풀이와 결과가 같았다. 7단계의 두 가지 실수가 1단계 판에서 틀리는 것과 2단계의 길 수도 확인했다. 50×50 판 23개의 시간도 쟀다 — 30_pg1839_p1.py

  1. 프로그래머스 스쿨, “튜브의 소개팅” (https://school.programmers.co.kr/learn/courses/30/lessons/1839), 2026-10-01 조회. ↩