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

미로 탈출 (Maze Solver)

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

01 Explore How It Works

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 Understand It Simply

For Everyone

🔑Analogy

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

💡In Plain Words

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

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

📍Where It's Used

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

03 Python Implementation

A clean, readable reference implementation of the core logic of 미로 탈출 (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 Frequently Asked Questions

FAQ

What is 미로 탈출 (Maze Solver)?+

What is the time complexity of 미로 탈출 (Maze Solver)?+

The time complexity of 미로 탈출 (Maze Solver) is O(4^(N·M)). Follow the step-by-step visualization to see exactly why.

Where is 미로 탈출 (Maze Solver) used?+

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

What's a simple analogy for 미로 탈출 (Maze Solver)?+

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

→ Backtracking — see allRelated

Guide Progress0%