파이썬 코딩테스트 강좌, 경로 찾기

문제 설명

주어진 2D 배열에서 시작점에서 도착점까지의 경로를 찾는 문제입니다. 이 배열은 통로와 장애물로 구성되어 있으며, 통로는 0으로, 장애물은 1로 표시됩니다.

목표는 주어진 시작점에서 도착점까지 이동할 수 있는 경로가 있는지를 판단하고, 가능한 경로를 출력하는 것입니다. 이동은 상하좌우로 가능합니다.

문제 정의

    def find_path(maze, start, end):
        """
        :param maze: 2D list representing the maze
        :param start: Tuple of (x, y) coordinates for the start point
        :param end: Tuple of (x, y) coordinates for the end point
        :return: List of tuples representing the path or None if no path exists
        """
    

문제 예시

    maze = [
        [0, 1, 0, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [1, 1, 0, 0, 0],
        [0, 0, 0, 1, 1]
    ]
    start = (0, 0)  # 시작점
    end = (4, 4)    # 도착점
    

예상 결과:
[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4)]

문제 해결 방안

이 문제는 깊이 우선 탐색(DFS)이나 너비 우선 탐색(BFS) 알고리즘을 통해 해결할 수 있습니다. 여기에선 DFS를 사용하여 경로를 찾는 방법을 설명하겠습니다.

깊이 우선 탐색(DFS) 알고리즘

DFS는 가능한 경로를 모두 탐색하면서 도착점에 도달하는지 여부를 판단합니다. 경로를 찾는 동안 방문한 노드를 기록하여 반복 방문을 방지합니다.

구현 단계

1단계: 기본 설정

먼저, 기본적인 설정을 통해 미로와 출발점 및 도착점을 정의합니다.

    maze = [
        [0, 1, 0, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [1, 1, 0, 0, 0],
        [0, 0, 0, 1, 1]
    ]
    start = (0, 0)
    end = (4, 4)
    

2단계: DFS 함수 정의

DFS를 통해 경로를 찾는 함수를 구현합니다.

    def dfs(maze, current, end, path, visited):
        if current == end:
            return path
        
        x, y = current
        visited.add(current)

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            next_x, next_y = x + dx, y + dy
            
            if 0 <= next_x < len(maze) and 0 <= next_y < len(maze[0]):
                if maze[next_x][next_y] == 0 and (next_x, next_y) not in visited:
                    result = dfs(maze, (next_x, next_y), end, path + [(next_x, next_y)], visited)
                    if result is not None:
                        return result
        
        visited.remove(current)
        return None
    

3단계: 경로 찾기 함수 구현

최종적으로 경로 찾기 함수를 구현하여 DFS를 호출합니다.

    def find_path(maze, start, end):
        visited = set()
        return dfs(maze, start, end, [start], visited)
    

4단계: 결과 출력

함수를 호출하여 결과를 출력합니다.

    path = find_path(maze, start, end)
    print("경로:", path)
    

전체 코드

    def dfs(maze, current, end, path, visited):
        if current == end:
            return path
        
        x, y = current
        visited.add(current)

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            next_x, next_y = x + dx, y + dy
            
            if 0 <= next_x < len(maze) and 0 <= next_y < len(maze[0]):
                if maze[next_x][next_y] == 0 and (next_x, next_y) not in visited:
                    result = dfs(maze, (next_x, next_y), end, path + [(next_x, next_y)], visited)
                    if result is not None:
                        return result
        
        visited.remove(current)
        return None

    def find_path(maze, start, end):
        visited = set()
        return dfs(maze, start, end, [start], visited)

    maze = [
        [0, 1, 0, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [1, 1, 0, 0, 0],
        [0, 0, 0, 1, 1]
    ]
    start = (0, 0)
    end = (4, 4)
    path = find_path(maze, start, end)
    print("경로:", path)