Algorithm Guidecomplexity: O(4^(N·M))

미로 탈출 (Maze Solver)

격자 미로에서 출발점부터 도착점까지의 경로를 찾는 문제입니다. 한 방향으로 나아가다 벽이나 막다른 길을 만나면 마지막 갈림길로 되돌아가며 다른 방향을 시도하는 백트래킹으로 해결합니다.

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

Maze Solver · 백트래킹

미로 탈출. 출발 S에서 도착 G까지, 한 방향으로 나아가다 막히면 마지막 갈림길로 되돌아갑니다.

Logic Node1 / 7

Live Python

1def solve(r, c):

2 if out_of_bounds(r, c) or grid[r][c] == WALL:

3 return False

4 if (r, c) in visited:

5 return False

6 visited.add((r, c)); path.append((r, c))

7 if (r, c) == goal:

8 return True

9 for dr, dc in [(1,0), (0,1), (-1,0), (0,-1)]:

10 if solve(r + dr, c + dc):

11 return True

12 path.pop() # 막다른 길 → 되돌아가기

13 return False

02 쉽게 이해하기

For Everyone

🔑비유

미로에서 한 길로 들어갔다 막히면 마지막 갈림길로 되돌아오는 것과 같습니다.

💡쉽게 말하면

한 방향으로 끝까지 가보고, 막다른 길이면 마지막 갈림길로 돌아와 다른 방향을 시도합니다(DFS 백트래킹).

모든 길을 체계적으로 훑어요.

📍어디에 쓰나

–경로 찾기
–미로·퍼즐
–게임 AI 길찾기

03 파이썬 구현 코드

미로 탈출 (Maze Solver)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

def solve_maze(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    path = []
    seen = set()

    def backtrack(r, c):
        if not (0 <= r < rows and 0 <= c < cols):
            return False
        if grid[r][c] != 0 or (r, c) in seen:
            return False
        seen.add((r, c)); path.append((r, c))
        if (r, c) == goal:
            return True
        for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            if backtrack(r + dr, c + dc):
                return True
        path.pop()       # 막다른 길 → 되돌아가기
        return False

    return path if backtrack(*start) else None

Guide Progress0%