자바스크립트 코딩테스트 강좌, 미로 탐색하기

안녕하세요! 이번 강좌에서는 자바스크립트를 이용한 알고리즘 문제, 특히 “미로 탐색하기”에 대해 깊이 있는 해설을 진행하겠습니다. 코딩테스트에서 빈번히 등장하는 문제 유형 중 하나로, 주어진 미로에서 출발점에서 도착점까지의 경로를 찾는 것이 목표입니다. 이 문제는 BFS(너비 우선 탐색) 또는 DFS(깊이 우선 탐색)와 같은 그래프 탐색 알고리즘을 적용하여 해결할 수 있습니다.

문제 설명

문제: 주어진 2차원 배열로 구성된 미로에서 시작점 (start)에서 도착점 (end)까지 도달할 수 있는 경로가 존재하는지 확인하세요. 미로에서의 경로는 ‘0’ (이동 가능한 공간)을 따라갈 수 있으며, ‘1’ (장애물)은 지나갈 수 없습니다.

예를 들어, 다음과 같은 미로가 주어졌다고 가정합니다:

[
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0]
]

시작점은 (0, 0)이고 도착점은 (4, 4)입니다. 즉, 미로를 탐색하여 (0, 0)에서 (4, 4)까지 갈 수 있는 경로가 존재하는지를 알아내야 합니다.

입력 및 출력

입력: 2차원 배열 (maze), 시작점 (start), 도착점 (end)
출력: 경로 존재 여부 (true/false)

문제 풀이 접근법

이 문제를 해결하기 위해 BFS(너비 우선 탐색) 또는 DFS(깊이 우선 탐색) 알고리즘을 사용할 수 있습니다. BFS는 최단 경로를 찾는 데 적합하지만, 이 문제에서는 경로의 존재 여부만 확인할 것이므로 DFS를 통해도 문제를 해결할 수 있습니다.

알고리즘 설명

1. **기본 설정**: 미로를 탐색하기 위해 다음과 같은 과정이 필요합니다.

탐색할 모든 노드를 스택에 추가합니다 (DFS의 경우).
탐색한 노드는 방문한 위치로 표시하여 중복 탐색을 방지합니다.
현재 위치에서 이동할 수 있는 모든 방향 (상, 하, 좌, 우)으로 진행합니다.
목표 위치에 도달하면 true를 반환합니다.
모든 경로를 탐색하고도 목표에 도달하지 못하면 false를 반환합니다.

자바스크립트 구현

이제 위의 알고리즘을 자바스크립트로 구현해 보겠습니다. 아래는 미로 탐색을 위한 DFS 알고리즘의 구체적인 코드입니다:


function isPathExist(maze, start, end) {
    const rows = maze.length;
    const cols = maze[0].length;

    // 이동 방향 배열 (상, 하, 좌, 우)
    const directions = [
        [-1, 0], // 상
        [1, 0],  // 하
        [0, -1], // 좌
        [0, 1]   // 우
    ];

    // 스택 초기화 및 방문 배열 설정
    const stack = [start];
    const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
    visited[start[0]][start[1]] = true;

    // DFS 탐색
    while (stack.length > 0) {
        const [x, y] = stack.pop();

        // 도착점에 도달한 경우
        if (x === end[0] && y === end[1]) {
            return true;
        }

        // 각 방향으로 이동
        for (const [dx, dy] of directions) {
            const newX = x + dx;
            const newY = y + dy;

            // 범위 체크 및 방문 확인
            if (newX >= 0 && newX < rows && newY >= 0 && newY < cols &&
                maze[newX][newY] === 0 && !visited[newX][newY]) {
                visited[newX][newY] = true;
                stack.push([newX, newY]);
            }
        }
    }

    // 도달할 수 없는 경우
    return false;
}

// 테스트
const maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0]
];
console.log(isPathExist(maze, [0, 0], [4, 4])); // true

코드 설명

위의 코드는 DFS(깊이 우선 탐색)를 이용하여 주어진 미로에서 시작점에서 도착점까지의 경로를 찾는 과정을 구현하고 있습니다. 주요 단계는 다음과 같습니다:

초기 설정: 먼저, 미로의 행과 열의 수를 초기화하고 이동 방향을 배열로 설정합니다. 이동할 수 있는 방향은 상, 하, 좌, 우의 네 방향입니다.
스택 및 방문 배열 초기화: DFS를 위해 스택을 이용하여 경로를 탐색하고, 방문한 위치는 ‘true’로 표시합니다.
DFS 반복: 스택에서 위치를 pop하여 현재 위치를 가져와 도착점인지 확인합니다. 도착점에 도달하면 true를 반환합니다.
이동 가능성 체크: 이동 가능한 방향으로 각 방향을 모두 확인하고, 새 위치가 범위 내에 있으며, 장애물이 없고, 방문한 적이 없는 경우에만 스택에 추가합니다.

성능 분석

이 알고리즘의 시간 복잡도는 O(V+E)입니다. 여기서 V는 정점의 수 (즉, 미로의 모든 위치)이고, E는 간선의 수 (즉, 각 위치에서 이동 가능한 방향의 수)입니다. 최악의 경우 모든 위치를 탐색해야 하므로 이 복잡도가 필요합니다. 공간 복잡도는 O(V)로, 방문 배열을 위한 공간이 필요하기 때문입니다.

마무리

이번 강좌에서는 자바스크립트를 이용하여 미로 탐색 문제를 해결하는 방법에 대해 알아보았습니다. DFS 알고리즘을 통해 미로의 경로 존재 여부를 확인할 수 있는 기초적인 코드와 기법을 배웠습니다. 이러한 유형의 문제는 코딩 테스트에서 자주 출제되므로, 다양한 변형 문제를 풀어보며 자신감을 키워보시기 바랍니다.

다음 강좌에서는 더 복잡한 미로 탐색 문제 또는 다른 유형의 알고리즘 문제를 다룰 예정이니, 많은 관심 부탁드립니다!