자바스크립트 코딩테스트 강좌, 깊이 우선 탐색

문제: 미로 탐색

주어진 2차원 배열에서 출발점 (시작점)에서 도착점까지의 경로가 존재하는지를 확인하는 문제입니다. 배열의 값은 0 (통과 가능)과 1 (통과 불가능)으로 주어집니다. 출발점은 (0, 0)이고, 도착점은 (N-1, M-1)입니다. 상하좌우로만 이동할 수 있으며, 경로가 존재하면 true, 존재하지 않으면 false를 반환해야 합니다.

문제 예시

입력

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

출력

true

설명

위의 예시에서 출발점 (0, 0)에서 시작하여 (1, 1), (2, 1), (2, 2), (2, 3), (3, 3)으로 경로를 따라 가면 도착점 (3, 3)에 도달할 수 있습니다.

문제 해결 과정

1. 알고리즘의 개요

이 문제는 깊이 우선 탐색(DFS) 알고리즘을 통해 해결할 수 있습니다. DFS는 노드를 방문할 때 가능한 한 깊게 들어갔다가 더 이상 갈 수 없게 되면 다른 경로로 돌아오는 방식입니다. 우리는 재귀를 사용하여 구현할 것입니다. DFS를 적용하여 미로를 탐색하고, 출발점에서 도착점까지 도달 가능한지를 확인합니다.

2. DFS 알고리즘 구현

DFS를 구현하기 위해서는 다음과 같은 단계가 필요합니다:

현재 위치가 경계 내에 있는지 확인합니다.
현재 위치가 통과 불가능한 지점인지 확인합니다.
현재 위치가 도착지인지 확인합니다.
현재 위치를 방문 처리합니다.
상하좌우 방향으로 재귀적으로 DFS를 호출합니다.
모든 경로를 탐색한 후 방문 처리를 해제합니다.

3. 코드 구현

다음은 자바스크립트를 이용한 DFS 알고리즘을 구현한 코드입니다:


function isPathExists(maze) {
    const rows = maze.length;
    const cols = maze[0].length;

    function dfs(x, y) {
        // 경계 조건
        if (x < 0 || y < 0 || x >= rows || y >= cols) return false;
        // 통과 불가능한 지점
        if (maze[x][y] === 1) return false;
        // 도착지
        if (x === rows - 1 && y === cols - 1) return true;

        // 현재 위치 방문 처리
        maze[x][y] = 1;

        // 상하좌우 DFS 탐색
        const found = dfs(x + 1, y) || dfs(x - 1, y) || dfs(x, y + 1) || dfs(x, y - 1);

        // 방문 처리 해제
        maze[x][y] = 0;

        return found;
    }

    return dfs(0, 0);
}

// 예제 테스트
const maze = [
    [0, 0, 1, 0],
    [1, 0, 1, 0],
    [0, 0, 0, 0],
    [0, 1, 1, 0]
];

console.log(isPathExists(maze)); // 출력: true

4. 코드 설명

코드의 주요 부분을 설명하겠습니다:

경계 조건 체크: 현재 위치가 배열의 경계를 초과하지 않는지 확인합니다.
통과 불가능한 지점 검사: 현재 위치의 값이 1인지 확인하여 통과 가능한 지점인지 검사합니다.
도착지 도달: 현재 위치가 도착점 (N-1, M-1)이라면 true를 반환합니다.
방문 처리: 현재 위치를 방문 처리하여 중복 탐색을 방지합니다.
재귀 호출: 상하좌우 방향으로 DFS를 재귀적으로 호출하여 경로를 탐색합니다.
방문 해제: 탐색이 끝난 후 방문 처리를 해제합니다.

5. 시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N * M)입니다. 여기서 N은 행의 수, M은 열의 수입니다. 모든 셀을 한 번씩 방문할 수 있기 때문입니다. 하지만 재귀에 따른 스택 공간 오버헤드로 인해 최악의 경우 필요할 수 있는 추가 메모리도 존재합니다.

결론

이번 강좌에서는 깊이 우선 탐색(DFS)을 통해 미로 탐색 문제를 해결하는 방법을 배웠습니다. DFS는 복잡한 그래프 구조에서도 유용하게 사용될 수 있으며, 다양한 문제에 적용할 수 있습니다. DFS의 특징과 동작 방식을 이해했다면, 다양한 문제에 응용해보는 것이 좋습니다. 다음 강좌에서는 너비 우선 탐색(BFS) 알고리즘에 대해 알아보겠습니다. 이 강좌가 도움이 되었기를 바랍니다.