[프로그래머스] 미로 탈출

상현·2023년 11월 15일

BFS 코딩테스트 프로그래머스

코딩테스트

목록 보기

18/30

[level 2] 미로 탈출 - 159993

문제 링크

성능 요약

메모리: 33.4 MB, 시간: 0.34 ms

구분

코딩테스트 연습 > 연습문제

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2023년 11월 3일 11:40:26

문제 설명

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

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

제한사항

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

입출력 예

maps	result
["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"]	16
["LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"]	-1

입출력 예 설명

입출력 예 #1

주어진 문자열은 다음과 같은 미로이며

다음과 같이 이동하면 가장 빠른 시간에 탈출할 수 있습니다.

4번 이동하여 레버를 당기고 출구까지 이동하면 총 16초의 시간이 걸립니다. 따라서 16을 반환합니다.

입출력 예 #2

주어진 문자열은 다음과 같은 미로입니다.

시작 지점에서 이동할 수 있는 공간이 없어서 탈출할 수 없습니다. 따라서 -1을 반환합니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

최종 제출

function solution(maps) {    
    const dx = [0, 0, 1, -1];
    const dy = [1, -1, 0, 0];
    
    // map을 새로 만든다.
    let newMaps = maps.map(m => m.split(""));
    
    let [columnLength, rowLength] = [newMaps[0].length, newMaps.length];

  	// BFS로 끝 지점 까지 찾아가는 여정...
    const find = (node, end) => {
        let queue = [node];
        // 지나온 배열 초기화
        let visitedArray = [...newMaps].map(m => m = [...newMaps[0]].fill(false));
        
        while (queue.length > 0) {
            let [x, y, count] = queue.shift();
          
            // 끝 지점에 왔으면 count return
            // 가장 짧은 count가 가장 먼저 return 될 것이다.
            if (newMaps[y][x] === end) return count; 
            
            count++;
            
            for (let i = 0; i < dx.length; i++) {
                const nx = x + dx[i];
                const ny = y + dy[i];

                if (nx >= columnLength || nx < 0) continue;
                if (ny >= rowLength || ny < 0) continue;
                
                if (visitedArray[ny][nx]) continue;
                if (newMaps[ny][nx] === "X") continue;
              
                // 방문하기 전에 미리 갔다고 표시해주자. 그래야 시간 초과 안남
                visitedArray[ny][nx] = true;
                
                queue.push([nx, ny, count]);
            }
        }
        

        return -1;
    }
    
    let startPosition; // start point 기억
    let leverPosition; // lever point 기억

    for (let x = 0; x < columnLength; x++) {
        for (let y = 0; y < rowLength; y++) {
            let c = newMaps[y][x];
            
            if (c === "S") {
                startPosition = [x, y, 0];
            } else if (c === "L") {
                leverPosition = [x, y, 0];
            }
            
            if (startPosition && leverPosition) break;
        }
    }
    
    // start -> lever
    let c1 = find(startPosition, 'L');
    if (c1 === -1) return -1;
    
    // lever -> exit
    let c2 = find(leverPosition, 'E');
    if (c2 === -1) return -1;
    
    
    return Number.isNaN(c1 + c2) ? -1 : c1 + c2;
    
}