프로그래머스 기차 선로 풀이: DFS와 백트래킹으로 경로 세기
작성·코드 검증: solve together · 작성 언어: Python
0. 문제 링크와 출처
- 문제: 기차 선로
- 출처: 프로그래머스, 2025 카카오 하반기 2차
- 자체 판단 난이도: Level 4
현재 칸에 들어온 방향에 따라 가능한 선로를 제한하면서 경로를 DFS로 구성해야 하고, 빈칸의 선로 선택·재방문·3번 십자 선로의 추가 통과 횟수를 함께 관리해야 한다. 단순한 경로 탐색이 아니라 여러 상태와 복원 규칙을 결합한 백트래킹이 필요하므로 Level 4로 판단했다.
이 글은 문제의 조건을 바탕으로 풀이 아이디어와 Python 구현을 정리한 글이다.
1. 문제 요약
격자에는 이미 놓인 선로, 빈칸, 장애물이 있다. 빈칸에는 선로를 놓지 않거나 1~7번 선로 중 하나를 놓을 수 있다.
기차는 왼쪽 위 (1, 1)에서 오른쪽으로 출발해 선로를 따라 움직이고, 오른쪽 아래 (n, m)에 도착해야 한다. 이때 이미 놓여 있거나 새로 놓은 모든 선로를 한 번 이상 지나야 한다. 3번 선로는 상하좌우가 모두 연결된 십자 선로이므로, 기차가 이 칸을 두 방향으로 지나야 조건을 만족한다.
격자의 크기는 최대 8×8이지만 실제 칸 수는 20 이하다. 빈칸마다 선로 7종류를 전부 시도하면 경우의 수가 너무 커지므로, 유효한 경로를 만들면서 필요한 선로만 선택해야 한다.
2. 문제 해결에 사용되는 알고리즘과 자료구조
후보 생성과 검증
선로 배치를 먼저 전부 만들고 마지막에 경로를 검사하면 빈칸의 조합이 폭발한다. 대신 기차가 현재 칸에 들어온 방향을 기준으로 다음 이동을 결정한다.
예를 들어 기차가 왼쪽에서 현재 칸으로 들어왔다면, 현재 칸에는 다음 선로만 놓을 수 있다.
- 가로 직선: 오른쪽으로 계속 이동
- 왼쪽-위쪽 코너: 위로 이동
- 왼쪽-아래쪽 코너: 아래로 이동
이렇게 하면 빈칸에서도 최대 3가지 선택만 탐색하면 된다. 경로에 실제로 포함된 빈칸에만 선로를 배치하므로, 경로에 포함되지 않은 빈칸은 자동으로 비워 둔 하나의 배치로 처리된다.
선로 연결을 방향으로 표현하기
재귀 함수의 direction은 현재 칸으로 들어온 방향이다.
1: 왼쪽에서 들어옴, 오른쪽으로 진행
2: 위에서 들어옴, 아래쪽으로 진행
3: 오른쪽에서 들어옴, 왼쪽으로 진행
4: 아래쪽에서 들어옴, 위쪽으로 진행고정 선로가 현재 방향과 연결되지 않으면 즉시 해당 탐색을 중단한다. 선로 번호 1과 2는 각각 가로·세로 직선이고, 3번은 네 방향이 모두 연결된 십자다. 4~7번은 네 종류의 코너다.
빈칸 재방문 처리
빈칸에 놓은 선로는 경로를 만들기 위해 선택한 순간에만 기록한다. 코너는 지나간 뒤 다시 사용할 수 없지만, 직선 선로는 직진 방향으로 한 번 더 통과할 수 있다.
따라서 used 배열에는 다음 상태만 저장한다.
0: 아직 선로를 선택하지 않은 빈칸3: 직선 선로로 선택되어 재방문 가능4,5,6,7: 코너로 선택되어 재방문 불가
3번 선로를 두 번 세는 이유
고정 선로를 지나간 횟수를 required에 저장한다. 일반 선로는 한 번, 3번 십자 선로는 두 번 더해야 한다.
십자 선로에서 가로 방향으로 지나간 뒤 세로 방향으로도 지나야 하므로, 단순히 칸 하나를 방문했다고 세면 모든 연결을 사용했는지 확인할 수 없다. 반면 새로 선택한 빈칸은 직선 또는 코너로만 사용되므로 한 번씩만 세면 된다.
DFS 상태의 불변식
이 탐색의 상태는 (현재 칸, 진입 방향, 고정 선로 통과 수, used)로 볼 수 있다. 진입
방향은 현재 칸에서 연결 가능한 다음 선로를 제한하고, used는 빈칸에 놓은 선로와 재방문
가능 여부를 기록한다. 따라서 빈칸 전체의 배치를 미리 만들지 않고 실제 경로에 나타난
선로만 분기하면 된다.
count는 입력에 이미 놓인 고정 선로를 지나간 횟수다. 새 선로는 선택하는 분기에서 바로
통과하므로 별도로 세지 않는다. 고정된 3번 십자 선로는 두 방향을 모두 지나야 하므로
필요 통과 수를 2로 잡는다. 반면 빈칸에 놓은 직선은 같은 방향으로 재진입할 수 있어
used[x][y] == 3으로 표시하고, 코너는 재진입을 막는다.
빈칸에 놓은 선로는 현재 재귀 경로에만 유효하다. 분기가 끝나면 used[x][y]를 0으로
되돌려 다음 분기가 그 칸을 다른 방향으로 선택할 수 있게 한다. 복원하지 않으면 이전
분기의 선택이 남아 다른 유효한 경로를 차단한다.
오답 접근과 반례
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 제한을 전제로 설계된 풀이다.
복사해 실행할 테스트
아래 검사는 시작 칸이 곧 도착 칸인 최소 격자 경계를 확인한다. 풀이 코드 아래에 붙여 python 파일명.py로 실행한다.
assert solution([[1, 7], [-1, 2]]) == 14. 참고 풀이 비교
- dh-winternagi의 풀이는 고정 선로의 개수를 미리 세고, 3번 선로를 두 번 세어 모든 연결 방향을 사용했는지 확인한다.
다른 풀이들과 이 글의 구현은 모두 같은 핵심을 공유한다. 차이는 언어별 자료구조와 분기 표현 방식이다. 일부 풀이는 선로 종류를 직접 분기하고, 다른 풀이는 방향 비트마스크로 연결 관계를 표현할 수 있다. 비트마스크를 사용하면 연결 여부를 일반화하기 쉽지만, 이 문제처럼 선로 종류가 7개로 고정된 경우에는 방향별 분기가 읽고 검증하기 더 간단하다.
마무리
이 문제의 핵심은 빈칸에 무엇을 놓을지 먼저 결정하는 것이 아니라, 기차가 실제로 지나갈 수 있는 경로를 먼저 탐색하는 것이다. 현재 진입 방향을 상태로 사용하면 가능한 선로가 자연스럽게 제한되고, 3번 십자 선로는 필요한 방문 횟수를 두 번으로 계산해 조건을 확인할 수 있다.