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

미로 탈출 (Maze Solver)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

HOVER OR SCROLL

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

04 자주 묻는 질문

FAQ

미로 탈출 (Maze Solver)란 무엇인가요?+

미로 탈출 (Maze Solver)의 시간복잡도는 어떻게 되나요?+

미로 탈출 (Maze Solver)의 시간복잡도는 O(4^(N·M)) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

미로 탈출 (Maze Solver)은(는) 어디에 사용하나요?+

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

미로 탈출 (Maze Solver)를 쉽게 비유하면?+

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

Guide Progress0%