프로그래머스

프로그래머스 기차 선로 풀이: DFS와 백트래킹으로 경로 세기

2026년 9월 1일

작성자: solve together · 작성 언어: Python

0. 문제 링크와 출처

문제: 기차 선로
출처: 프로그래머스, 2025 카카오 하반기 2차
자체 판단 난이도: Level 4

이 글은 문제의 조건을 바탕으로 풀이 아이디어와 Python 구현을 정리한 글입니다. 문제 원문과 제한 조건은 변경될 수 있으므로 제출 전에는 반드시 원문을 다시 확인하세요.

1. 문제 요약

격자에는 이미 놓인 선로, 빈칸, 장애물이 있습니다. 빈칸에는 선로를 놓지 않거나 1~7번 선로 중 하나를 놓을 수 있습니다.

기차는 왼쪽 위 (1, 1)에서 오른쪽으로 출발해 선로를 따라 움직이고, 오른쪽 아래 (n, m)에 도착해야 합니다. 이때 이미 놓여 있거나 새로 놓은 모든 선로를 한 번 이상 지나야 합니다. 3번 선로는 상하좌우가 모두 연결된 십자 선로이므로, 기차가 이 칸을 두 방향으로 지나야 조건을 만족합니다.

격자의 크기는 최대 8×8이지만 실제 칸 수는 20 이하입니다. 빈칸마다 선로 7종류를 전부 시도하면 경우의 수가 너무 커지므로, 유효한 경로를 만들면서 필요한 선로만 선택해야 합니다.

2. 문제 해결에 사용되는 알고리즘과 자료구조

경로 중심의 DFS

선로 배치를 먼저 전부 만들고 마지막에 경로를 검사하면 빈칸의 조합이 폭발합니다. 대신 기차가 현재 칸에 들어온 방향을 기준으로 다음 이동을 결정합니다.

예를 들어 기차가 왼쪽에서 현재 칸으로 들어왔다면, 현재 칸에는 다음 선로만 놓을 수 있습니다.

가로 직선: 오른쪽으로 계속 이동
왼쪽-위쪽 코너: 위로 이동
왼쪽-아래쪽 코너: 아래로 이동

이렇게 하면 빈칸에서도 최대 3가지 선택만 탐색하면 됩니다. 경로에 실제로 포함된 빈칸에만 선로를 배치하므로, 경로에 포함되지 않은 빈칸은 자동으로 비워 둔 하나의 배치로 처리됩니다.

선로 연결을 방향으로 표현하기

재귀 함수의 direction은 현재 칸으로 들어온 방향입니다.

1: 왼쪽에서 들어옴, 오른쪽으로 진행
2: 위에서 들어옴, 아래쪽으로 진행
3: 오른쪽에서 들어옴, 왼쪽으로 진행
4: 아래쪽에서 들어옴, 위쪽으로 진행

고정 선로가 현재 방향과 연결되지 않으면 즉시 해당 탐색을 중단합니다. 선로 번호 1과 2는 각각 가로·세로 직선이고, 3번은 네 방향이 모두 연결된 십자입니다. 4~7번은 네 종류의 코너입니다.

빈칸 재방문 처리

빈칸에 놓은 선로는 경로를 만들기 위해 선택한 순간에만 기록합니다. 코너는 지나간 뒤 다시 사용할 수 없지만, 직선 선로는 직진 방향으로 한 번 더 통과할 수 있습니다.

따라서 used 배열에는 다음 상태만 저장합니다.

0: 아직 선로를 선택하지 않은 빈칸
3: 직선 선로로 선택되어 재방문 가능
4, 5, 6, 7: 코너로 선택되어 재방문 불가

3번 선로를 두 번 세는 이유

고정 선로를 지나간 횟수를 required에 저장합니다. 일반 선로는 한 번, 3번 십자 선로는 두 번 더해야 합니다.

십자 선로에서 가로 방향으로 지나간 뒤 세로 방향으로도 지나야 하므로, 단순히 칸 하나를 방문했다고 세면 모든 연결을 사용했는지 확인할 수 없습니다. 반면 새로 선택한 빈칸은 직선 또는 코너로만 사용되므로 한 번씩만 세면 됩니다.

핵심 관찰

빈칸의 선로 종류를 먼저 모두 정하면 대부분의 조합이 실제 출발 경로와 무관해집니다. 현재 칸에 들어온 방향을 상태로 삼으면 연결 가능한 선로만 분기할 수 있고, 경로에 포함되지 않은 빈칸은 그대로 두는 것으로 처리됩니다. 3번 선로는 두 방향의 연결을 모두 사용해야 하므로 방문 횟수를 2로 세어야 합니다.

오답 접근과 반례

3번 선로를 다른 고정 선로처럼 한 번만 방문했다고 세면 모든 연결을 사용했는지 판정할 수 없습니다. 예를 들어 기차가 십자 선로를 가로 방향으로만 지나간 뒤 도착해도 한 번으로 세면 조건을 통과시키지만, 세로 방향 연결은 아직 사용하지 않은 상태입니다.

3. 문제 해결 코드 (Python)

def solution(grid):
    n = len(grid)
    m = len(grid[0])

    # 바깥 경계를 장애물로 채워 이동 가능 여부를 별도로 검사하지 않습니다.
    tracks = [[-1] * (m + 2) for _ in range(n + 2)]
    for i in range(n):
        for j in range(m):
            tracks[i + 1][j + 1] = grid[i][j]

    required = 0
    for row in grid:
        for tile in row:
            if tile == 3:
                required += 2
            elif tile > 0:
                required += 1

    # 빈칸에 새로 선택한 선로의 종류를 저장합니다.
    used = [[0] * (m + 2) for _ in range(n + 2)]
    answer = 0

    # direction: 1=왼쪽에서, 2=위에서, 3=오른쪽에서, 4=아래에서 진입
    def dfs(direction, x, y, count):
        nonlocal answer

        if tracks[x][y] == -1:
            return

        # 도착 칸에서는 마지막 선로가 출구 방향으로 연결되는지도 확인합니다.
        if x == n and y == m:
            if count == required:
                if direction == 1 and tracks[x][y] == 1:
                    answer += 1
                elif direction == 2 and tracks[x][y] == 2:
                    answer += 1
            return

        tile = tracks[x][y]

        if direction == 1:
            if tile == 1 or tile == 3:
                dfs(1, x, y + 1, count + 1)
            elif tile == 4:
                dfs(4, x - 1, y, count + 1)
            elif tile == 7:
                dfs(2, x + 1, y, count + 1)
            elif tile == 0:
                if used[x][y] == 3:
                    dfs(1, x, y + 1, count)
                elif used[x][y] == 0:
                    used[x][y] = 3
                    dfs(1, x, y + 1, count)
                    used[x][y] = 4
                    dfs(4, x - 1, y, count)
                    used[x][y] = 7
                    dfs(2, x + 1, y, count)
                    used[x][y] = 0

        elif direction == 2:
            if tile == 2 or tile == 3:
                dfs(2, x + 1, y, count + 1)
            elif tile == 4:
                dfs(3, x, y - 1, count + 1)
            elif tile == 5:
                dfs(1, x, y + 1, count + 1)
            elif tile == 0:
                if used[x][y] == 3:
                    dfs(2, x + 1, y, count)
                elif used[x][y] == 0:
                    used[x][y] = 3
                    dfs(2, x + 1, y, count)
                    used[x][y] = 4
                    dfs(3, x, y - 1, count)
                    used[x][y] = 5
                    dfs(1, x, y + 1, count)
                    used[x][y] = 0

        elif direction == 3:
            if tile == 1 or tile == 3:
                dfs(3, x, y - 1, count + 1)
            elif tile == 5:
                dfs(4, x - 1, y, count + 1)
            elif tile == 6:
                dfs(2, x + 1, y, count + 1)
            elif tile == 0:
                if used[x][y] == 3:
                    dfs(3, x, y - 1, count)
                elif used[x][y] == 0:
                    used[x][y] = 3
                    dfs(3, x, y - 1, count)
                    used[x][y] = 5
                    dfs(4, x - 1, y, count)
                    used[x][y] = 6
                    dfs(2, x + 1, y, count)
                    used[x][y] = 0

        else:  # direction == 4
            if tile == 2 or tile == 3:
                dfs(4, x - 1, y, count + 1)
            elif tile == 6:
                dfs(1, x, y + 1, count + 1)
            elif tile == 7:
                dfs(3, x, y - 1, count + 1)
            elif tile == 0:
                if used[x][y] == 3:
                    dfs(4, x - 1, y, count)
                elif used[x][y] == 0:
                    used[x][y] = 3
                    dfs(4, x - 1, y, count)
                    used[x][y] = 6
                    dfs(1, x, y + 1, count)
                    used[x][y] = 7
                    dfs(3, x, y - 1, count)
                    used[x][y] = 0

    # 시작 칸은 1번 선로이고, 기차는 오른쪽으로 출발합니다.
    dfs(1, 1, 1, 1)
    return answer

복잡도

빈칸마다 모든 선로를 독립적으로 고르는 방식이 아니라, 현재 진입 방향에 연결되는 최대 3가지 선택만 탐색합니다. 따라서 단순한 7^k 완전탐색보다 훨씬 적은 상태를 방문합니다. 다만 경로 조합을 탐색하는 백트래킹이므로 일반적인 최악의 경우는 지수 시간이며, 이 문제의 n × m ≤ 20 제한을 전제로 설계된 풀이입니다.

4. 다른 풀이 방식 검색 및 요약

웹에서 확인한 공개 풀이들은 공통적으로 선로 배치를 모두 만든 뒤 검증하지 않고, 출발점에서 기차의 이동 경로를 바로 DFS로 생성하는 방식을 사용했습니다.

프로그래머스 질문 게시판의 풀이 아이디어는 경로에 대응하는 선로 배치가 사실상 하나이므로, 경로 중심으로 접근하면 중복 탐색을 줄일 수 있다고 설명합니다.
dh-winternagi의 풀이는 고정 선로의 개수를 미리 세고, 3번 선로를 두 번 세어 모든 연결 방향을 사용했는지 확인합니다.

다른 풀이들과 이 글의 구현은 모두 같은 핵심을 공유합니다. 차이는 언어별 자료구조와 분기 표현 방식입니다. 일부 풀이는 선로 종류를 직접 분기하고, 다른 풀이는 방향 비트마스크로 연결 관계를 표현할 수 있습니다. 비트마스크를 사용하면 연결 여부를 일반화하기 쉽지만, 이 문제처럼 선로 종류가 7개로 고정된 경우에는 방향별 분기가 읽고 검증하기 더 간단합니다.

마무리

이 문제의 핵심은 빈칸에 무엇을 놓을지 먼저 결정하는 것이 아니라, 기차가 실제로 지나갈 수 있는 경로를 먼저 탐색하는 것입니다. 현재 진입 방향을 상태로 사용하면 가능한 선로가 자연스럽게 제한되고, 3번 십자 선로는 필요한 방문 횟수를 두 번으로 계산해 조건을 확인할 수 있습니다.