문제 접근
이 문제는 빈칸에 선로를 놓아서 기차가 (1, 1)에서 출발해 (n, m)까지 도착할 수 있는 경우의 수를 구하는 문제다.
기차는 항상 현재 진행 방향을 가지고 움직인다.
따라서 빈칸에 선로를 놓을 때도 모든 선로를 다 시도할 필요 없이, 현재 진행 방향에서 진입 가능한 선로만 놓아보면 된다.
예를 들어 기차가 오른쪽으로 이동 중이라면, 현재 칸에는 오른쪽 방향으로 진입 가능한 선로만 놓을 수 있다.
방향 정의
방향은 다음과 같이 정의한다.
RIGHT, LEFT, DOWN, UP = 0, 1, 2, 3
dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]
## 선로 표현
방향을 숫자로 표현한다.각 방향의 의미는 다음과 같다.
RIGHT: 오른쪽
LEFT : 왼쪽
DOWN : 아래
UP : 위현재 방향에서 놓을 수 있는 선로
기차가 어떤 방향으로 들어오느냐에 따라 놓을 수 있는 선로가 달라진다.
def is_valid_rail(rail, direction):
if rail == 1:
return direction in (RIGHT, LEFT)
if rail == 2:
return direction in (UP, DOWN)
if rail == 3:
return True
if rail == 4:
return direction in (RIGHT, DOWN)
if rail == 5:
return direction in (LEFT, DOWN)
if rail == 6:
return direction in (LEFT, UP)
if rail == 7:
return direction in (RIGHT, UP)
return False3번 선로는 상하좌우 모든 방향으로 연결되어 있으므로 항상 진입 가능하다.
다음 위치 구하기
현재 칸의 선로에 따라 기차의 다음 진행 방향이 바뀔 수 있다.
직선 선로인 1, 2, 십자 선로인 3은 방향이 그대로 유지된다.
코너 선로인 4 ~ 7은 방향을 꺾어주어야 한다.
def next_state(y, x, direction):
rail = grid[y][x]
if rail == 4:
direction = LEFT if direction == DOWN else UP
elif rail == 5:
direction = RIGHT if direction == DOWN else UP
elif rail == 6:
direction = RIGHT if direction == UP else DOWN
elif rail == 7:
direction = LEFT if direction == UP else DOWN
return y + dy[direction], x + dx[direction], direction모든 선로를 방문했는지 확인
문제 조건상 기차는 격자에 존재하는 모든 선로를 한 번 이상 지나야 한다.
또한 3번 선로는 상하좌우가 모두 연결되어야 하므로, 코드에서는 3번 선로를 두 번 방문해야 조건을 만족한 것으로 처리했다.
def visited_all_rails():
for y in range(n):
for x in range(m):
if 1 <= grid[y][x] <= 7:
if grid[y][x] == 3:
if visited[y][x] != 2:
return False
elif visited[y][x] < 1:
return False
return TrueDFS 탐색
DFS에서는 현재 위치와 진행 방향을 기준으로 탐색한다.
현재 칸이 빈칸이면 현재 방향에서 놓을 수 있는 선로를 하나씩 놓아본다.
이미 선로가 있는 칸이면 현재 방향과 연결되는지 확인한 뒤 다음 칸으로 이동한다.
도착점에 도달하면 모든 선로를 방문했는지 확인하고, 조건을 만족하면 정답을 1 증가시킨다.
전체 코드
def solution(grid):
n, m = len(grid), len(grid[0])
# 방향: 오른쪽, 왼쪽, 아래, 위
RIGHT, LEFT, DOWN, UP = 0, 1, 2, 3
dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]
# 현재 진행 방향으로 진입했을 때 놓을 수 있는 선로
placeable = {
RIGHT: [1, 3, 4, 7],
LEFT: [1, 3, 5, 6],
DOWN: [2, 3, 4, 5],
UP: [2, 3, 6, 7],
}
visited = [[0] * m for _ in range(n)]
visited[0][0] = 1
visited[n - 1][m - 1] = 1
answer = 0
def is_valid_rail(rail, direction):
if rail == 1:
return direction in (RIGHT, LEFT)
if rail == 2:
return direction in (UP, DOWN)
if rail == 3:
return True
if rail == 4:
return direction in (RIGHT, DOWN)
if rail == 5:
return direction in (LEFT, DOWN)
if rail == 6:
return direction in (LEFT, UP)
if rail == 7:
return direction in (RIGHT, UP)
return False
def next_state(y, x, direction):
rail = grid[y][x]
if rail == 4:
direction = LEFT if direction == DOWN else UP
elif rail == 5:
direction = RIGHT if direction == DOWN else UP
elif rail == 6:
direction = RIGHT if direction == UP else DOWN
elif rail == 7:
direction = LEFT if direction == UP else DOWN
return y + dy[direction], x + dx[direction], direction
def visited_all_rails():
for y in range(n):
for x in range(m):
if 1 <= grid[y][x] <= 7:
if grid[y][x] == 3:
if visited[y][x] != 2:
return False
elif visited[y][x] < 1:
return False
return True
def dfs(y, x, direction):
nonlocal answer
if y < 0 or y >= n or x < 0 or x >= m:
return
if grid[y][x] == -1:
return
if y == n - 1 and x == m - 1:
if is_valid_rail(grid[y][x], direction) and visited_all_rails():
answer += 1
return
visited[y][x] += 1
if grid[y][x] == 0:
for rail in placeable[direction]:
grid[y][x] = rail
ny, nx, nd = next_state(y, x, direction)
dfs(ny, nx, nd)
grid[y][x] = 0
else:
if is_valid_rail(grid[y][x], direction):
ny, nx, nd = next_state(y, x, direction)
dfs(ny, nx, nd)
visited[y][x] -= 1
# 시작점 (0,0)의 1번 선로에서 오른쪽으로 출발
dfs(0, 1, RIGHT)
return answer정리
이 풀이의 핵심은 빈칸 전체를 무작정 채우는 것이 아니라, 기차가 이동하는 경로를 따라가며 필요한 칸에만 선로를 놓아보는 것이다.
현재 진행 방향을 기준으로 놓을 수 있는 선로를 제한하면 탐색 범위를 줄일 수 있다.
또한 도착점에 도달했을 때 모든 선로를 방문했는지 검사하여 문제 조건을 만족하는 경우만 정답에 포함한다.
