[프로그래머스] Level2 - 미로 탈출(Javascript)

프로그래머스

 

📝 문제 요약

1️⃣ 1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 한다. 각 칸은 통로 또는 벽으로 구성되어 있다.

2️⃣ 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있다. 

3️⃣ 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 된다.

4️⃣ 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구해라.

5️⃣ 만약 미로를 탈출할 수 없으면 -1을 return해라.

 

❌ 실패 코드

function solution(maps) {
    // 1.문자열 => 배열
    const maps_split = maps.map((e) => e.split(""));
    
    // 간편하게 쓰려고 n, m으로 이름 바꿨다
    const n = maps_split.length;
    const m = maps_split[0].length;
    
    // 출발지점을 큐에 담기
    let start = [];
    let lever = [];
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            // 출발지점 시작지점에 담기
            if (maps_split[i][j] === "S") {
                start.push(i, j);
            }
            
            
        }
    }
    
    // 결과 도출
    return bfs(start, "E", maps_split, n, m)   
}

// bfs 시작
function bfs(start, target, maps_split, n, m) {
    // Array.from(Array(row), () => Array(col).fill())방식으로 2차원 배열 만들기 
    let visited = Array.from(Array(n), () => Array(m).fill(false)); 
    let queue = [];
    let [a, b] = start
        
    // 시작지점 표시
    visited[a][b] = true;
    
    // queue 시작지점과 최소 시간을 계산하기 위해 변수를 넣는다. 
    queue.push([a, b, 0])
        
        
    // 큐가 있을때까지
    while (queue.length > 0) {
    // 미로를 탐색할 위치 x,y 값
        let [x, y, time] = queue.shift();
        // 만약에 x랑 y가 종료 지점이면 answer을 return하고 break
        if (maps_split[x][y] === target) {
            return time
        }

            // 사방탐색
            const dx = [0, 0, -1, 1]
            const dy = [-1, 1, 0, 0]

            // 탐색을 위해서 다음 지점
            for (let d = 0; d < 4; d++) {
                let nx = x + dx[d];
                let ny = y + dy[d];


                // 범위 벗어나지 않고 방문한 적 없을 때
                if (nx > -1 && nx < n && ny >-1 && ny < m && !visited[nx][ny]) {
                    // 통로랑 레버일 경우 다음 로직 실행
                    if (maps_split[nx][ny] !== "X") {
                        // 방문 표시
                        visited[nx][ny] = true
                        // 다음 미로를 탐색
                        queue.push([nx, ny, time+1]);
                    }
                }

            }
        
    }
    // while문을 통과를 못할 경우 탈출 할 수 없으니 -1을 return 
    return -1;
}

❗️실패 원인

👉 문제를 제대로 좀 읽자... 기존의 BFS 코드와 비슷한 문제지만 미로로 가는 도중에 레버가 있는 칸으로 가서 레버를 당겨야 한다. 

 

✅ 정답 코드

function solution(maps) {
    // 1.문자열 => 배열
    const maps_split = maps.map((e) => e.split(""));
    
    // 간편하게 쓰려고 n, m으로 이름 바꿈
    const n = maps_split.length;
    const m = maps_split[0].length;

    // 출발지점을 큐에 담기
    let start = [];
    let lever = [];
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            // 출발지점 시작지점에 담기
            if (maps_split[i][j] === "S") {
                start.push(i, j);
            }
            // 레버지점에서 다시 시작지점에 담기
            if (maps_split[i][j] === "L") {
                lever.push(i, j);
            }
        }
    }
    
    // 출발지점 ~ 레버지점까지의 시간 계산
    let result1 = bfs(start, "L", maps_split, n, m);
    // 레버지점부터 ~ 도착지점까지의 시간 계산
    let result2 = bfs(lever, "E", maps_split, n, m);

    
    // 두 경로 중에 -1이라면 탈출할 방법이 없으므로 -1을 return 
    if (result1 === -1 || result2 === -1) {
        return -1
    }

    // 도착지점까지 잘 간다면 두 지점의 시간을 더해준다.
    return result1 + result2
   
}

// bfs 함수
function bfs(start, target, maps_split, n, m) {
    // Array.from(Array(row), () => Array(col).fill())방식으로 2차원 배열 만들기 
    let visited = Array.from(Array(n), () => Array(m).fill(false)); 
    let queue = [];
    let [a, b] = start
        
    // 시작지점 표시
    visited[a][b] = true;
    
    // queue 시작지점과 최소 시간을 계산하기 위해 변수를 넣는다. 
    queue.push([a, b, 0])
        
        
    // 큐가 있을때까지
    while (queue.length > 0) {
    // 미로를 탐색할 위치 x,y 값
        let [x, y, time] = queue.shift();
        // 만약에 x랑 y가 종료 지점이면 answer을 return하고 break
        if (maps_split[x][y] === target) {
            return time
        }

            // 사방탐색
            const dx = [0, 0, -1, 1]
            const dy = [-1, 1, 0, 0]

            // 탐색을 위해서 다음 지점
            for (let d = 0; d < 4; d++) {
                let nx = x + dx[d];
                let ny = y + dy[d];


                // 범위 벗어나지 않고 방문한 적 없을 때
                if (nx > -1 && nx < n && ny >-1 && ny < m && !visited[nx][ny]) {
                    // 통로랑 레버일 경우 다음 로직 실행
                    if (maps_split[nx][ny] !== "X") {
                        // 방문 표시
                        visited[nx][ny] = true
                        // 다음 미로를 탐색
                        queue.push([nx, ny, time+1]);
                    }
                }

            }
        
    }
    // while문을 통과를 못할 경우 탈출 할 수 없으니 -1을 return 
    return -1;
}

 

🖨️ 실행결과

 

📔느낀점

👉 문제를 제발 끝까지 읽자... 문제를 제대로 안 읽으면 시간이 오래 걸린다. 

👉 오랜만에 BFS를 풀었는데 이전에 많이 다뤄봐서 그런지 코드를 짜는데 큰 어려움은 없었다.