우리가 미로에 갇힌 게임을 하고 있다고 가정해 봅시다. 우리는 미로에서 탈출구를 찾아야 합니다. 미로는 xm 행렬로 나타낼 수 있습니다. 여기서 n은 행 수이고 m은 열 수입니다. 행렬의 각 셀/요소에는 'O', 'D', 'S' 또는 '-' 기호가 포함됩니다. 'O'는 길이 막혔음을 의미하고, 'D'는 미로에서 나가는 길, 'S'는 우리의 시작 위치, '-'는 경로를 통해 이동할 수 있음을 의미합니다. '-'로 표시된 셀을 통해 자유롭게 이동할 수 있습니다. 이제 미로에서 출구 경로('D' 셀)를 찾을 수 있는 나침반도 있습니다. 방향을 찾아야 할 때는 나침반을 사용해야 합니다. 그러나 나침반은 최대 k번 사용할 수 있습니다. 미로를 행렬로 사용하고 나침반을 사용할 수 있는 횟수가 주어집니다. 나침반을 그렇게 많이 사용해서 미로를 빠져나갈 수 있을지 알아내야 한다. 가능하면 True를 반환하고 그렇지 않으면 False를 반환합니다.
따라서 입력이 grid =
와 같은 경우| - | O | - | O | - | - | - | - | - | - | O |
| - | O | D | - | O | - | O | O | O | - | O |
| - | O | O | - | O | - | O | O | O | - | O |
| - | O | O | - | O | - | O | S | - | - | - |
| - | - | - | - | - | - | O | O | O | O | - |
n =4, m =11, k =3; 그러면 출력이 True가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
path_search() 함수를 정의합니다. curr_pos, grid, total_rows, total_cols, k, 선행 작업이 필요합니다.
-
x:=curr_pos의 x 값
-
y:=curr_pos의 y 값
-
grid[x, y]가 "*"와 같으면
-
k가 0과 같으면
-
참을 반환
-
-
그렇지 않으면
-
거짓을 반환
-
-
그렇지 않으면
-
부모 :=전임자[curr_pos]
-
succ_pos :=succesor_positions(curr_pos, grid, total_rows, total_cols, parent)의 반환 값에서 새 목록
-
use_compass :=succ_pos의 크기가 1보다 크면 참
-
succ_pos의 각 위치에 대해 수행
-
전임자[위치] :=curr_pos
-
use_compass가 0이 아니면
-
path_search(위치, 그리드, total_rows, total_cols, k - 1, 선행 작업)
-
- 그렇지 않으면
-
path_search(위치, 그리드, total_rows, total_cols, k, 선행 작업)
-
-
-
-
-
-
succesor_positions() 함수를 정의합니다. curr_pos, grid, total_rows, total_cols, parent
가 필요합니다.-
x:=curr_pos의 x 값
-
y:=curr_pos의 y 값
-
succ_pos :=새 목록
-
o y> 0이면
-
왼쪽 :=x, y - 1
-
succ_pos의 끝에 왼쪽 삽입
-
-
y
-
오른쪽 :=x, y + 1
-
succ_pos의 끝에 바로 삽입
-
-
x> 0이면
-
위로 :=x - 1, y
-
succ_pos의 끝에 최대 삽입
-
-
x
-
아래로 :=x + 1, y
-
succ_pos의 끝에 아래로 삽입
-
-
succ_pos의 모든 위치에 대해 grid[position[0], pos[1]]가
인 경우 -
"X"와 같지 않고 pos가 부모와 같지 않은 경우 -
-
조건을 만족하는 succ_pos의 요소를 반환합니다.
-
-
이제 다음을 수행하십시오 -
-
curr_pos :=새로운 빈 쌍
-
각 인덱스 i, 그리드의 항목 행에 대해 수행
-
각 인덱스 j, 행의 항목 요소에 대해 수행
-
요소가 'M'과 같으면
-
curr_pos :=i, j를 포함하는 새 쌍
-
-
-
-
선행자 :=curr_pos :=처음에 Null인 새 맵
-
path_search(curr_pos, grid, n, m, k, 선행자)
소스 코드(Python)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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