파이썬 미로 탈출 경로 찾기 / 순열 생성하기

1. 미로 탈출 경로 찾기

문제 설명:

• N x M 크기의 미로가 주어집니다. 미로는 0과 1로 구성되어 있으며, 0은 이동할 수 없는 벽을 나타내고, 1은 이동할 수 있는 경로를 나타냅니다.
• 시작 위치는 (0, 0)이며, 미로의 출구는 (N-1, M-1)에 위치해 있습니다.
• 최단 경로로 미로를 탈출하는 방법을 찾는 프로그램을 작성하세요. 이동은 상하좌우로만 가능합니다.

 

요구사항:

1. BFS 알고리즘을 사용하여 미로의 모든 경로를 탐색합니다.
2. 시작 위치에서 출구까지의 최단 경로의 길이를 찾아야 합니다.
3. 최단 경로의 길이를 반환합니다.

 

예시 입력:

11101
10101
10101
11111

예시 출력:

8

• 시작 위치 (0, 0)에서 출구 (3, 4)까지의 최단 경로의 길이는 8입니다.

 

예시 입력:

11111
00001
11101
10001
11111

예시 출력:

14

• 시작 위치 (0, 0)에서 출구 (4, 4)까지의 최단 경로의 길이는 14입니다. 이 경로는 미로의 가장자리를 따라가면서, 필요한 곳에서만 안으로 들어가 출구에 도달하는 경로입니다.

 

생각해보기:

1. BFS 알고리즘을 이용하므로, 상하좌우로 움직이는 것을 생각해 자식노드는 부모노드의 상하좌우에 위치한것처럼 생각.

2. 노드에 길이를 저장하는 변수를 두어 따로 최솟값을 구하는 번거로움을 없앰.

 

 

아래는 답안 코드

from collections import deque

def bfs_maze_escape(maze):
    N, M = len(maze), len(maze[0])  # 미로의 크기
    visited = [[False] * M for _ in range(N)]  # 방문한 위치를 추적하는 배열
    queue = deque([(0, 0, 1)])  # 큐 초기화: 시작 위치와 경로 길이 (x, y, distance)
    visited[0][0] = True  # 시작 위치 방문 처리

    # 이동 가능한 방향: 상, 하, 좌, 우
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while queue:
        x, y, dist = queue.popleft()

        # 출구에 도달했다면 어차피 제일 처음 도달하여 최단 거리이므로 현재 경로 길이 반환
        if x == N-1 and y == M-1:
            return dist

        # 모든 가능한 방향으로 이동
        for dx, dy in directions:
            nx, ny = x + dx, y + dy

            # 이동 가능한 위치인지 확인하고, 아직 방문하지 않았다면 큐에 추가
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and maze[nx][ny] == "1":
                visited[nx][ny] = True
                queue.append((nx, ny, dist + 1))

    # 출구에 도달할 수 없는 경우
    return -1

# 예시 입력
maze = [
    "11101",
    "10101",
    "10101",
    "11111"
]

# 문자열을 리스트로 변환하여 입력
maze = [list(row) for row in maze]

# 함수 실행 및 결과 출력
print(bfs_maze_escape(maze))

 

 

2. 순열 생성하기

문제 설명:

• 주어진 정수 배열에서 모든 가능한 순열을 생성하는 프로그램을 작성하세요.
• 배열에는 중복된 숫자가 없다고 가정합니다.

 

요구사항:

1. 주어진 배열의 모든 숫자를 사용하여 만들 수 있는 모든 순열을 출력합니다.
2. 백트래킹 알고리즘을 사용하여 효율적으로 모든 가능성을 탐색합니다.

 

예시 입력:

[1, 2, 3]

예시 출력:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

• 주어진 배열 [1, 2, 3]으로 만들 수 있는 모든 순열을 출력합니다.

 

예시 입력:

[1, 2, 3, 4]

예시 출력:

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]

• 설명: 주어진 배열 [1, 2, 3, 4]로 만들 수 있는 모든 순열을 출력합니다. 배열의 모든 요소를 사용하여 가능한 모든 순서의 조합을 탐색하고 생성합니다.

생각해보기: 아래와 같이 DFS방식으로 내려가는데, 선택된 숫자는 배제하는 것을 고려(중복x) 

 

출처: https://velog.io/@1998yuki0331/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%9C%BC%EB%A1%9C-%EC%88%9C%EC%97%B4-%EC%A1%B0%ED%95%A9-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0

아래는 답안 코드

def permute(nums):
    def backtrack(start=0):
        # 모든 숫자가 순열에 포함되었을 때 결과를 추가
        if start == len(nums):
            result.append(nums[:])
            return

        for i in range(start, len(nums)):
            # 숫자 선택
            nums[start], nums[i] = nums[i], nums[start]
            # 다음 숫자로 넘어가며 백트래킹 실행
            backtrack(start + 1)
            # 선택 취소
            nums[start], nums[i] = nums[i], nums[start]

    result = []
    backtrack()
    return result


# 예시 실행
print(permute([1, 2, 3]))