[프그래머스 2단계] 미로 탈출

❓문제 설명

• 특정 의미를 가진 문자 구성된 문자열로 이루어진 배열을 하나 줌
• 미로탈출하는 것임 레버 당기고 S에서 E로 가는 최단시간을 구해야 함
• 탈출 못하는 경우에는 -1을 반환해야 함

✅ 문제 해결

• 탈출 못하는 경우를 먼저 생각해서 예외처리로 처리한 다음에 나머지를 처리해보자
• 탈출 못하는 경우: 레버 상하좌우로 X가 있을 경우랑 S지점 상하좌우로 X가 있는 경우
• 최단거리를 찾는 것은 어떻게 해야할까??? - 검색해보자 최소시간을 구하는 문제는 BFS로 풀라고 한다.

function solution(maps) {
    let cMaps = maps.map((e)=>[...e].map(a=>a))
    const bfs = (start, init = 0) => {
        cMaps[start[0]][start[1]] = init
        const [w, h] = [maps.length, maps[0].length],
              queue = [start]
        const [dirX, dirY] = [[0, 0, -1, 1], [-1, 1, 0, 0]]
        while (queue.length) {
            const [x, y] = queue.shift()
            for (let i =0; i < 4; i++) {
                const [dx, dy] = [x + dirX[i], y + dirY[i]]
                if (dx < 0 || dy < 0 || dx >= w || dy >= h) continue
                if (cMaps[dx][dy] === 'X' || cMaps[dx][dy] < 10000) continue
                else {
                    cMaps[dx][dy] = cMaps[x][y] + 1
                    queue.push([dx, dy])
                }
            }
        }
        return cMaps
    }
    
    
    const info = maps.reduce((acc, e, i)=> {
        for (let j= 0; j < e.length; j++) {
            if (e[j] === 'S' || e[j] === 'E' ||  e[j] === 'L') {
                acc[e[j]] = [i, j]
            }
        }
        return acc // 누적 객체를 반환하는 것이 중요한 것이구나
    }, {})
    let t = bfs(info.S)[info.L[0]][info.L[1]]
    if (t !== "L") {
        cMaps = maps.map((e)=>[...e].map(a=>a))
        t = bfs(info.L, t)[info.E[0]][info.E[1]]
    } else return -1
    return t !== 'E' ? t : -1
}

• BFS의 개념에 대해서 부족한 부분도 많아서 다른 코드를 참고하면서 만들어 봄

🔥 인상 깊은 남의 풀이

https://song-ift.tistory.com/342

https://yjg-lab.tistory.com/399    

 

• 코드에 대해서 참고를 하면서 각각 어떤 것을 의미하는지 이해하는데 초점을 많이 맞추게 되었다.

❕느낀점

• BFS와 DFS가 그래프 탐색 방법이고 이러한 방법을 통해서 최소횟수를 구할 때 어떤 알고리즘을 먼저 떠올려야하는 지 알 수 있었다.
• let, const를 통해서 재할당이 안되는 경우에 발생하는 에러에 대해서 이해도가 조금 더 좋아진 것 같다.
• 메서드를 다양하게 사용한 것은 아니지만 알고리즘 방식에 대해서 queue의 형식에 대해서 조금 더 이해할 수 있었다.