[프로그래머스LV2] 미로찾기 (bfs)

프로그래머스

 

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

---

제한사항

• 5 ≤ maps의 길이 ≤ 100
  • 5 ≤ maps[i]의 길이 ≤ 100
  • maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
    • S : 시작 지점
    • E : 출구
    • L : 레버
    • O : 통로
    • X : 벽
  • 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
  • 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

 

로직

1. 시작점, 레버, 출구 위치 파악

2. bfs를 통해 시작점에서 레버까지의 최소거리, 레버에서 출구까지 최소거리를 각각 구하기

3. 둘의 최소거리의 합을 리턴

 

주의할 점

• 레버를 당겨야 출구가 열린다.
• 출구가 레버보다 더 가까운데 있을 수 있다
• 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있다.
• 배열의 인덱스가 존재해야 배열[i][j]를 구할 수 있다. (따라서 먼저 i, j가 타당한지 검사한 뒤, 배열[i][j]가 타당한지 검사)
• 이차배열 초기화
  • new Array()  
  • Array.from() 

// 1. new Array
const newArray = new Array(3).fill().map((c) => new Array(5).fill(0));
// 2. Array.from
const fromArray = Array.from({ length: 3 }, () =>
  Array.from({ length: 5 }, () => 0)
);

fromArray[0][0] = 1;
newArray[0][0] = 1;
console.log(fromArray, newArray); // [ [ 1, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0 ] ]

 

 

테스트케이스

입력: ["SOOOO", "OOOOO", "OOOOO", "OOOOO", "OOOLE"]

기댓값: 18

출력: 8

 

입력:["SLXOX", "EXXXO", "OOOOO", "OXXXX", "OOOOO"]

기댓값: 3

출력: 1

 

 

문제 정리

- 먼저 레버를 당긴 후 출구로 나간다

- 미로를 빠져나가는데 필요한 최소시간 (bfs)

풀이

- 입구와 레버의 위치를 찾는다

- 시작점에서 목적지까지 이동하는데 필요한 최소시간을 구하는 함수를 만든다

  - 4방향 탐색하며 갈 수 있는 길을 queue에 넣는다

  - 배열외부이거나, X이거나, 이미 방문한 경우 갈 수 없는 길이다.

  - 목적지를 찾으면 최소시간을 리턴한다.

- 입구에서 레버까지 최소시간을 구한다.

- 레버에서 출구까지 최소시간을 구한다

- 위의 둘다 존재하면 둘의 합을 리턴, 하나라도 존재하지 않으면 -1을 리턴한다.

느낀 점

- 시작점에서 목적지까지 이동하는데 필요한 최소시간을 구하는 함수를 분리하여 쓰니 편했다.

- 여러번 지나갈 수 있어도 visited를 기록함으로써 무한반복을 방지하고 최소시간을 구할 수 있다.

배운 점

- 최소시간을 구하는 메소드

- 무한반복이 생기면 visited를 검사한다

 

전체코드

function solution(maps) {
    var answer = 0;
    let start, lever;
    const dr = [-1, 0, 1, 0];
    const dc = [0, 1, 0, -1];
    const rowLen = maps.length;
    const colLen = maps[0].length;
    
    // 시작, 레버위치 찾기
    for (let r = 0; r < maps.length; ++r) {
        for (let c = 0; c < maps[0].length; ++c) {
            if (maps[r][c] === 'S') start = {r, c};
            if (maps[r][c] === 'L') lever = {r, c};
        }
    }
    // 시작점에서 타겟까지 이동하는 최소시간 구하는 함수
    function getMinTime(start, target) {
        const queue = [{r: start.r, c: start.c, time: 0}];
        const visited = Array.from({length: rowLen}, () => Array.from({length: colLen}, () => false)); 
        visited[start.r][start.c] = true;
        
        while(queue.length) {
            const curr = queue.shift();
            // 목표물 찾으면 걸린시간 리턴
            if (maps[curr.r][curr.c] === target) {
                return curr.time;
            }
            // 다음위치 탐색
            for (let i = 0; i < 4; i++) {
                const nextR = curr.r + dr[i];
                const nextC = curr.c + dc[i];
                // 배열 외부
                if (nextR < 0 || nextR >= rowLen || nextC < 0 || nextC >= colLen) continue;
                // 벽이거나 이미 방문했음
                if (maps[nextR][nextC] === 'X' || visited[nextR][nextC]) continue;
                visited[nextR][nextC] = true; // 방문표시
                queue.push({r: nextR, c: nextC, time: curr.time + 1});
            }
            
        }
    }
    const timeToLever = getMinTime(start, 'L', maps); // 입구에서 레버까지 최소시간 
    const timeToExit = getMinTime(lever, 'E', maps); // 레버에서 출구까지 최소시간 
    return timeToLever && timeToExit ? timeToLever + timeToExit: -1;
}