문제 보기 · Level 3 · 2020 카카오 인턴십 · 정답률 49% · 푼 사람 9,189명 (2026-09-30 기준)1

문제

N×N 격자(0은 빈칸, 1은 벽)에서 (0, 0)부터 (N − 1, N − 1)까지 상하좌우로 이어지는 경주로를 짓는다. 이웃한 두 칸을 잇는 직선 도로 하나는 100원이고, 두 직선 도로가 직각으로 만나는 코너 하나마다 500원이 더 든다. 최소 건설 비용을 돌려준다.

  • 3 ≤ N ≤ 25
  • 출발점과 도착점은 늘 빈칸이고, 늘 이을 수 있다

풀이

막히면 한 단계씩 펼친다.

필요한 개념

다익스트라: 한 칸 가는 비용이 100원 또는 600원으로 달라서 BFS가 아니라 다익스트라다. 비용이 “들어온 방향”에 따라 달라지니, 점을 (칸, 들어온 방향)으로 잡는다.

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

3×3 빈 판에서 오른쪽으로 두 칸, 아래로 두 칸 가면 직선 도로 4개(400원)와 코너 1개(500원)로 900원이다. 지그재그로 가면 코너가 늘어 더 비싸다.

비용을 셀 때 “직선 도로 한 칸마다 100원, 방향을 바꾸는 칸마다 500원 더”로 보면 된다. 즉 한 칸 갈 때 앞 칸과 같은 방향이면 100원, 다른 방향이면 600원이다.

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

겹치지 않는 경로를 모두 만들어 비용을 세면, 25×25 판에서는 경로 수가 폭발한다. 칸마다 “여기까지 오는 최소 비용” 하나만 기억하고 다익스트라를 돌리면 빠르지만, 아래 3단계의 이유로 틀린다.

3단계 · 핵심 아이디어
  • 칸 하나에 비용 하나로는 모자라다: 같은 칸에 같은 비용으로 도착해도, 들어온 방향에 따라 다음 칸의 비용이 달라진다. 오른쪽으로 들어왔으면 계속 오른쪽은 100원, 아래로 꺾으면 600원이다.
  • 점 = (칸, 들어온 방향): 상태를 칸 N²개 × 방향 4개로 늘린다. 이 상태 그래프에서 간선 비용은 100 또는 600이고 모두 0 이상이라 다익스트라가 맞다.
  • 출발: (0, 0)에는 방향이 없다. 첫 걸음은 어느 방향이든 100원이다.
  • 답: (N − 1, N − 1)에 네 방향으로 들어온 비용 중 가장 작은 값이다.
4단계 · 코드 흐름
  1. cost[r][c][d]를 무한대로 채운다(d: 들어온 방향 0 ~ 3).
  2. (0, 0)의 네 이웃 중 빈칸에 100원을 적고 힙에 넣는다.
  3. 힙에서 (비용, r, c, d)를 꺼낸다. 낡았으면 버린다. 네 방향으로 가 보며, 같은 방향이면 +100, 다르면 +600으로 줄여 본다.
  4. cost[N − 1][N − 1]의 네 값 중 가장 작은 값을 돌려준다.
5단계 · 파이썬 코드 
import heapq

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))                 # 아래, 위, 오른쪽, 왼쪽

def solution(board):
    N = len(board)
    INF = float("inf")
    cost = [[[INF] * 4 for _ in range(N)] for _ in range(N)]
    heap = []
    for d, (dr, dc) in enumerate(DIRS):                    # 첫 걸음은 100원
        r, c = dr, dc
        if 0 <= r < N and 0 <= c < N and board[r][c] == 0:
            cost[r][c][d] = 100
            heapq.heappush(heap, (100, r, c, d))
    while heap:
        w, r, c, d = heapq.heappop(heap)
        if w > cost[r][c][d]:                              # 낡은 기록
            continue
        for nd, (dr, dc) in enumerate(DIRS):
            nr, nc = r + dr, c + dc
            if 0 <= nr < N and 0 <= nc < N and board[nr][nc] == 0:
                nw = w + (100 if nd == d else 600)         # 꺾으면 코너 500원 더
                if nw < cost[nr][nc][nd]:
                    cost[nr][nc][nd] = nw
                    heapq.heappush(heap, (nw, nr, nc, nd))
    return min(cost[N - 1][N - 1])
  • enumerate(DIRS): 방향 번호 d와 (dr, dc)를 함께 준다.
  • [[[INF] * 4 for _ in range(N)] for _ in range(N)]: N×N×4 표다. 안쪽부터 “방향 4칸”, “한 줄 N칸”, “N줄”이다.
  • 되돌아가는 방향(오른쪽으로 왔다가 왼쪽)도 600원으로 계산되지만, 이런 길은 늘 손해라 답에 영향이 없다.
6단계 · 실행 추적

칸마다 비용 하나만 기억하면 틀리는 판이다.

0 0 1
0 0 0
0 1 0
상태 (칸, 들어온 방향) 최소 비용 어떻게
(1, 0), 아래 100 출발 → 아래
(0, 1), 오른쪽 100 출발 → 오른쪽
(1, 1), 아래 700 (0, 1)에서 꺾어 아래
(1, 1), 오른쪽 700 (1, 0)에서 꺾어 오른쪽
(1, 2), 오른쪽 800 (1, 1) 오른쪽에서 곧장
(2, 2), 아래 1400 (1, 2)에서 꺾어 아래

답은 1400이다. (1, 1)에 두 방향이 모두 700원으로 도착한다. 칸마다 값 하나만 기억하면 먼저 적힌 “아래로 들어옴”만 남는다. 그러면 (1, 2)로 가려면 꺾어야 해 1300원, 다시 꺾어 (2, 2)에 1900원이 된다.

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

상태 4N²개, 상태마다 간선 4개라 \(O(N^2 \log N)\)다. N = 25면 상태 2,500개로 금방 끝난다.

  • 칸마다 비용 하나만 기억한다(6단계). 이렇게 짜면 문제의 예시 3번(답 2100)에서도 틀린다.
  • 비용이 달라지는데 BFS로 “먼저 도착한 값”을 확정한다.
  • 출발점의 방향을 하나로 정해(예: 오른쪽) 첫 걸음을 아래로 갈 때 코너 비용을 붙인다.
검증: 문제의 예시 4개를 통과했다. 무작위 판 600개(N = 3 ~ 5)에서 “상태별 비용을 더 줄지 않을 때까지 되풀이해 줄이는” 풀이, “겹치지 않는 칸 경로를 모두 만들어 세는” 풀이와 결과가 모두 같았다. 6단계 표의 값과, 칸마다 비용 하나만 기억하면 6단계 판에서 1900이 나오고 예시 3번도 틀리는 것을 확인했다 — 26_pg67259_p1.py

  1. 프로그래머스 스쿨, “경주로 건설” (https://school.programmers.co.kr/learn/courses/30/lessons/67259), 2026-09-30 조회. ↩