[프로그래머스] 연습문제 / 미로탈출 / Lv2 / JS / 접근법, 문제풀이 공유

 

---

문제 이해하기

주어진 문제는 다음과 같습니다:

• 미로는 O(빈칸), X(벽), S(시작점), L(레버), E(출구)로 구성됩니다.
• S에서 L로, L에서 E로 이동해야 합니다.
• O만 지나갈 수 있으며, X는 벽이라 지나갈 수 없습니다.
• 최단 거리로 이동하는 방법을 찾는 게 목표입니다.

예제 입력

["SOOOL",  "XXXXO",  "OOOOO",  "OXXXX",  "OOOOE"]​

 

 

위 미로에서 우리는 S(0, 0) → L(0, 4) → E(4, 4)로 이동하는 경로를 찾아야 합니다.

출처: 프로그래머스(https://school.programmers.co.kr/learn/courses/30/lessons/159993)

---

알고리즘을 어떻게 접근할까?

이 문제를 해결하기 위해 두 가지 개념을 사용합니다:
1. 미로 탐색
2. 최단 거리 찾기

최단 거리 탐색에 적합한 BFS

최단 거리를 찾기 위해 BFS (Breadth-First Search), 즉 너비 우선 탐색을 사용합니다. BFS는 가까운 곳부터 차례로 탐색하며 최단 경로를 보장하는 장점이 있습니다.

---

코드 작성하기

1. 미로에서 주요 위치 찾기

미로에서 S, L, E의 좌표를 찾습니다.

let start, lever, end;

// S, L, E의 위치를 찾기
maps.forEach((row, rowIndex) => {
    if (row.includes('S')) start = [rowIndex, row.indexOf('S')];
    if (row.includes('L')) lever = [rowIndex, row.indexOf('L')];
    if (row.includes('E')) end = [rowIndex, row.indexOf('E')];
});

 

---

2. BFS 함수 작성하기

BFS는 큐(queue)를 이용해 진행합니다.
다음 코드를 통해 start에서 destination까지 최단 거리를 계산합니다.

function bfs(start, destination) {
    const queue = [[...start, 0]]; // [x, y, 거리]
    const visited = Array.from({ length: maps.length }, () =>
        Array(maps[0].length).fill(false)
    );
    visited[start[0]][start[1]] = true;

    while (queue.length) {
        const [x, y, dist] = queue.shift();

        // 목적지 도착 시 거리 반환
        if (x === destination[0] && y === destination[1]) return dist;

        // 상하좌우 탐색
        for (const [dx, dy] of [[0, 1], [1, 0], [0, -1], [-1, 0]]) {
            const nx = x + dx;
            const ny = y + dy;

            // 이동 가능 조건 확인
            if (
                nx >= 0 && nx < maps.length &&
                ny >= 0 && ny < maps[0].length &&
                maps[nx][ny] !== 'X' &&
                !visited[nx][ny]
            ) {
                visited[nx][ny] = true;
                queue.push([nx, ny, dist + 1]);
            }
        }
    }

    return -1; // 목적지에 도달 불가
}

 

---

3. 경로 계산하기

이제 S → L과 L → E로 나눠 계산합니다.

const toLever = bfs(start, lever); // S에서 L까지
const toExit = bfs(lever, end);   // L에서 E까지

if (toLever === -1 || toExit === -1) {
    return -1; // 도달 불가능
}
return toLever + toExit;

 

---

코드 전체

최종 코드는 다음과 같습니다:

function solution(maps) {
    let start, lever, end;

    maps.forEach((row, rowIndex) => {
        if (row.includes('S')) start = [rowIndex, row.indexOf('S')];
        if (row.includes('L')) lever = [rowIndex, row.indexOf('L')];
        if (row.includes('E')) end = [rowIndex, row.indexOf('E')];
    });

    function bfs(start, destination) {
        const queue = [[...start, 0]];
        const visited = Array.from({ length: maps.length }, () =>
            Array(maps[0].length).fill(false)
        );
        visited[start[0]][start[1]] = true;

        while (queue.length) {
            const [x, y, dist] = queue.shift();
            if (x === destination[0] && y === destination[1]) return dist;

            for (const [dx, dy] of [[0, 1], [1, 0], [0, -1], [-1, 0]]) {
                const nx = x + dx;
                const ny = y + dy;

                if (
                    nx >= 0 && nx < maps.length &&
                    ny >= 0 && ny < maps[0].length &&
                    maps[nx][ny] !== 'X' &&
                    !visited[nx][ny]
                ) {
                    visited[nx][ny] = true;
                    queue.push([nx, ny, dist + 1]);
                }
            }
        }

        return -1;
    }

    const toLever = bfs(start, lever);
    const toExit = bfs(lever, end);

    if (toLever === -1 || toExit === -1) return -1;
    return toLever + toExit;
}

 

---

알고리즘 TIP 💡

1. BFS와 DFS의 차이:
   DFS는 끝까지 파고드는 방식으로 탐색합니다. 반면, BFS는 가까운 거리부터 탐색하므로 최단 거리 문제에 적합합니다.
2. 방문 처리:
   이미 방문한 곳을 다시 방문하면 무한 루프에 빠질 수 있습니다. visited 배열로 방문 여부를 기록하세요.
3. 큐(queue) 사용:
   BFS는 큐를 사용해 탐색의 순서를 관리합니다. 배열의 shift와 push로 쉽게 구현할 수 있습니다.

---

마치며

오늘은 미로에서 최단 거리를 찾는 방법을 알아보았습니다. BFS를 활용하면 미로 같은 문제를 효율적으로 해결할 수 있어요.