프로그래머스 미궁 탈출 lv2(javascript)

프로그래머스 연습문제 미궁 탈출 lv2

거의 3개월 넘게 알고리즘 문제를 풀지 않아서 감각을 다 잃었다.

감각을 살릴 겸 일주일에 3~4문제정도는 프로그래머스와 백준 문제 쉬운 것들을 풀어보려고 한다!

미궁탈출 lv2 문제 요약

lv4 문제 아님

요약하면 매우 간단하다.

• 2차원 행렬의 미궁이 있고 시작지점 / 레버 / 도착지점이 주어진다.
• X(벽)은 못지나간다.
• 벽이 아니면 어디든 여러번 지나갈 수 있다.
• 시작지점에서 레버를 찍고 도착지점으로 도착했을 때 거리를 구해라

결국 그래프 시작지점에서 도착까지 최단거리를 구하는 것이기 때문에 BFS를 사용하면 편하다.

레버를 누르고 난 뒤의 도착지점을 구해야되기 때문에 까다로워보일 수 있지만

해당 요구사항을 나눠서 생각해보면 편하다.

시작지점에서 레버에 도착하기까지 최단거리를 구한다.

레버에서 도착지점에 도착하기까지 최단거리를 구한다

즉 시작지점에서 도착지점까지의 최단거리를 구하는 BFS함수를 만들어 두번 돌리면 된다.

도착지점은 행렬 마지막 위치고 시작지점, 레버 는 모두 우리가 직접 행렬에서 찾아야한다.

둘 다 먼저 찾아놓은 다음 활용하던 시작지점만 찾고 레버에 도착하면 위치를 반환하게 하던 상관없을 것 같다.

풀이코드

const X = [0, 0, 1, -1];
const Y = [1, -1, 0, 0];

const queueInstance = () => {
    const storage = {};
    let head = 0;
    let tail = 0;
    
    function offer(element) {
        storage[tail++] = element;
    }
    
    function poll() {
        const removedElement = storage[head];
        delete storage[head++];
        return removedElement;
    }
    
    function isEmpty() {
        return head === tail;
    }
    
    return {offer, poll, isEmpty};
}

function solution(maps) {
    const startPoint = findStartPoint(maps);
    const leverTravelResult = bfs(maps, startPoint, 'L');
    if(!leverTravelResult) {
        return -1;
    }
    const destinationTravelResult = bfs(maps, leverTravelResult.point, 'E');
    return destinationTravelResult ? destinationTravelResult.count + leverTravelResult.count : -1;
}

function bfs(maps, start, destination) {
    const xLim = maps.length;
    const yLim = maps[0].length;
    const visited = [...new Array(xLim)].map(v => Array.from({length: yLim}, () => false));
    const queue = queueInstance();
    queue.offer([...start, 0]);
    while(!queue.isEmpty()) {
        const [currentX, currentY, count] = queue.poll();
        if(visited[currentX][currentY]) {
            continue;
        }
        visited[currentX][currentY] = true;
        if(maps[currentX][currentY] === destination) {
            return {point: [currentX, currentY], count};
        }
        for(let i = 0; i < 4; i ++) {
            const newPointX = currentX + X[i];
            const newPointY = currentY + Y[i];
            if(!isValidPoint(newPointX, newPointY, xLim, yLim)) {
                continue;
            }
            if(!visited[newPointX][newPointY] && !hasWall(newPointX, newPointY, maps)) {
                queue.offer([newPointX, newPointY, count + 1]);
            }
        }
    }
    return undefined;
}

function isValidPoint(x, y, xLim, yLim) {
    return x >= 0 && y >= 0 && x < xLim && y < yLim;
}

function hasWall(x, y, maps) {
    return maps[x][y] === 'X';
}

function findStartPoint(maps) {
    let x;
    const y = maps.findIndex(v => {
        const startX = v.indexOf('S');
        if(startX >= 0) {
            x = startX;
            return true;
        }
        return false;
    });
    return [y, x];
}

자바로 하면 필요없는데 자바스크립트로 하니 큐를 직접 만들어야 해서 귀찮다.

클로저 함수로 만들어 주었다.

bfs함수 내부에서는 시작지점에서부터 탐색을 시작해 방문여부와 거리정보를 계산하며 저장하고 이를 활용해 거리를 구한다.

주의할 것은 이 함수를 두번 사용하기 때문에 방문여부, 큐 같은 부가적인 정보들을 담은 변수의 생명주기가 해당 함수에서 끝나야 한다는 것이다.