[Programmers] (BFS) Lv 2. 미로 탈출

https://school.programmers.co.kr/learn/courses/30/lessons/159993

프로그래머스

 

javascript

닫기 줄바꿈

function solution(maps) {
​​​​const bfs = (s, e) => {
​​​​​​​​const [width, height] = [maps.length, maps[0].length],
​​​​​​​​​​​​[queue, valueVisit] = [[], maps.map((e) => [...e].map((v) => 0))];
​​​​​​​​const [dirX, dirY] = [[0, 0, -1, 1], [-1, 1, 0, 0]];

​​​​​​​​queue.push([s[0], s[1]]);

​​​​​​​​while (queue.length) {
​​​​​​​​​​​​const [x, y] = queue.shift();

​​​​​​​​​​​​for (let i = 0; i < 4; ++i) {
​​​​​​​​​​​​​​​​const [nx, ny] = [x + dirX[i], y + dirY[i]];

​​​​​​​​​​​​​​​​if (nx < 0 || ny < 0 || nx >= width || ny >= height) continue;
​​​​​​​​​​​​​​​​if (maps[nx][ny] === "X") continue;
​​​​​​​​​​​​​​​​if (valueVisit[nx][ny] && valueVisit[x][y] + 1 >= valueVisit[nx][ny]) continue;

​​​​​​​​​​​​​​​​valueVisit[nx][ny] = valueVisit[x][y] + 1;
​​​​​​​​​​​​​​​​queue.push([nx, ny]);
​​​​​​​​​​​​}
​​​​​​​​}

​​​​​​​​return valueVisit[e[0]][e[1]] === 0 ? -1 : valueVisit[e[0]][e[1]];
​​​​};

​​​​const pos = maps.reduce((acc, e, i) => ([...e].forEach((v, j) => {
​​​​​​​​​​​​​​​​​​​​if (["S", "L", "E"].includes(v)) acc[v] = [i, j];
​​​​​​​​​​​​​​​​}), acc), {});
​​​​const [dist1, dist2] = [bfs(pos["S"], pos["L"]), bfs(pos["L"], pos["E"])];
​​​​
​​​​return dist1 < 0 || dist2 < 0 ? -1 : dist1 + dist2;
}

GitHub : https://github.com/developeSHG/Algorithm-Baekjoon_Programmers/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/unrated/159993.%E2%80%85%EB%AF%B8%EB%A1%9C%E2%80%85%ED%83%88%EC%B6%9C/%EB%AF%B8%EB%A1%9C%E2%80%85%ED%83%88%EC%B6%9C.js

GitHub - developeSHG/Algorithm-Baekjoon_Programmers: 백준 and 프로그래머스 소스코드