파이썬으로 미로 탈출하기: 나침반 사용 횟수가 충분한지 확인하는 프로그램

문제 이해하기

미로에 갇힌 게임 상황을 생각해 봅시다. 우리는 미로에서 빠져나갈 출구를 찾아야 합니다. 미로는 n행 m열 크기의 행렬로 표현되며, 각 칸에는 다음 네 가지 기호 중 하나가 들어 있습니다.

• 'O' — 막힌 경로(지나갈 수 없음)
• 'D' — 미로의 출구
• 'S' — 플레이어의 시작 위치
• '-' — 자유롭게 이동할 수 있는 통로

우리는 출구('D')를 향한 방향을 찾기 위해 나침반을 사용할 수 있지만, 나침반은 최대 k번까지만 사용할 수 있다는 제약이 있습니다. 미로 정보와 나침반 사용 가능 횟수가 주어졌을 때, 주어진 횟수 안에서 미로를 빠져나올 수 있는지 판별하는 것이 이 문제의 목표입니다. 탈출이 가능하면 True, 불가능하면 False를 반환합니다.

입력 예시

예를 들어 다음과 같은 그리드가 주어진다고 해봅시다.

n = 4, m = 11, k = 3일 때, 출력은 True입니다.

풀이 접근 방법

이 문제는 깊이 우선 탐색(DFS)을 활용해 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. 현재 위치에서 이동할 수 있는 방향이 둘 이상이라면 어느 길로 갈지 선택해야 하므로 나침반을 사용해야 하고, 갈 수 있는 길이 하나뿐이라면 고민할 필요 없이 그 길로 이동하면 됩니다.

문제를 해결하기 위해 두 개의 함수를 정의합니다.

1. path_search() 함수

이 함수는 curr_pos(현재 위치), grid(미로), total_rows(전체 행 수), total_cols(전체 열 수), k(남은 나침반 사용 횟수), predecessor(이전 위치 정보)를 매개변수로 받습니다.

• 현재 위치의 x, y 좌표를 추출합니다.
• grid[x][y]가 'D'(출구)라면:
  • k가 0이면 True를 반환합니다. (정확히 허용된 횟수만큼 나침반을 사용해 도달)
  • 그렇지 않으면 False를 반환합니다.
• 출구가 아니라면:
  • parent := predecessor[curr_pos]로 이전 위치를 가져옵니다.
  • succ_pos := succesor_positions()의 반환값으로 다음 후보 위치 목록을 만듭니다.
  • use_compass := succ_pos의 크기가 1보다 크면 True (방향 선택이 필요함)
  • succ_pos의 각 위치에 대해:
    • predecessor[position] := curr_pos로 부모 정보를 갱신합니다.
    • use_compass가 참이면 path_search(position, grid, total_rows, total_cols, k - 1, predecessor)를 재귀 호출합니다.
    • 그렇지 않으면 path_search(position, grid, total_rows, total_cols, k, predecessor)를 호출합니다.

2. succesor_positions() 함수

이 함수는 curr_pos, grid, total_rows, total_cols, parent를 매개변수로 받아 현재 위치에서 이동 가능한 인접 칸들의 목록을 반환합니다.

• y > 0이면 왼쪽(left) := (x, y - 1)을 succ_pos에 추가합니다.
• y < total_cols - 1이면 오른쪽(right) := (x, y + 1)을 추가합니다.
• x > 0이면 위(up) := (x - 1, y)를 추가합니다.
• x < total_rows - 1이면 아래(down) := (x + 1, y)를 추가합니다.
• 마지막으로, 값이 'O'(막힌 칸)가 아니고 부모 위치와 같지 않은 칸들만 필터링하여 반환합니다.

실행 흐름

• 그리드를 순회하며 'S'의 위치를 찾아 curr_pos에 저장합니다.
• predecessor 맵을 {curr_pos: None}으로 초기화합니다.
• path_search(curr_pos, grid, n, m, k, predecessor)를 호출해 탐색을 시작합니다.

파이썬 소스 코드

아래 구현을 통해 더 잘 이해해 봅시다.

def path_search(curr_pos, grid, total_rows, total_cols, k, predecessor):
    x, y = curr_pos
    if grid[x][y] == "D":
        if k == 0:
            print('True')
        else:
            print('False')
    else:
        parent = predecessor[curr_pos]
        succ_pos = list(succesor_positions(curr_pos, grid, total_rows, total_cols, parent))
        use_compass = len(succ_pos) > 1
        for position in succ_pos:
            predecessor[position] = curr_pos
            if use_compass:
                path_search(position, grid, total_rows, total_cols, k - 1, predecessor)
            else:
                path_search(position, grid, total_rows, total_cols, k, predecessor)

def succesor_positions(curr_pos, grid, total_rows, total_cols, pred):
    x, y = curr_pos
    succ_pos = []
    if y > 0:
        left = (x, y - 1)
        succ_pos.append(left)
    if y < total_cols - 1:
        right = (x, y + 1)
        succ_pos.append(right)
    if x > 0:
        up = (x - 1, y)
        succ_pos.append(up)
    if x < total_rows - 1:
        down = (x + 1, y)
        succ_pos.append(down)
    return filter(lambda pos: grid[pos[0]][pos[1]] != "O" and pos != pred, succ_pos)

def solve(grid, n, m, k):
    curr_pos = ()
    for i, row in enumerate(grid):
        for j, element in enumerate(row):
            if element == 'S':
                curr_pos = (i, j)
    path_search(curr_pos, grid, n, m, k, predecessor={curr_pos: None})

grid = [['-', 'O', '-', 'O', '-', '-', '-', '-', '-', '-', 'O'],
['-', 'O', 'D', '-', 'O', '-', 'O', 'O', 'O', '-', 'O'],
['-', 'O', 'O', '-', 'O', '-', 'O', 'S', '-', '-', '-'],
['-', '-', '-', '-', '-', '-', 'O', 'O', 'O', 'O', '-']]

solve(grid, 4, 11, 3)

입력

grid = [['-', 'O', '-', 'O', '-', '-', '-', '-', '-', '-', 'O'],
['-', 'O', 'D', '-', 'O', '-', 'O', 'O', 'O', '-', 'O'],
['-', 'O', 'O', '-', 'O', '-', 'O', 'S', '-', '-', '-'],
['-', '-', '-', '-', '-', '-', 'O', 'O', 'O', 'O', '-']] , 4, 11, 3

출력

True