🔎 경주로 건설

❓ 문제링크

https://programmers.co.kr/learn/courses/30/lessons/67259

📄 제출 코드

function solution(board) {
    let map = board;
    bfs(0, 0, 0, -1, map);
    return answer;
}
let answer = Infinity;    
const dx = [1,-1,0,0];
const dy = [0,0,1,-1];
function bfs(x, y, cost, dir, map) {
    let q = [[x, y, cost, dir]];
    map[x][y] = 1;
    
    while (q.length > 0) {
        let cur = q.shift();
        let cur_x = cur[0];
        let cur_y = cur[1];
        let cur_cost = cur[2];
        let cur_dir = cur[3];
        if (cur_x == map.length - 1 && cur_y == map.length - 1) {
            answer = Math.min(answer, cur_cost);
            continue;
        }
        for (let i = 0; i < 4; i++) {
            let nx = cur_x + dx[i];
            let ny = cur_y + dy[i];
            if (nx >= 0 && nx < map.length && ny >= 0 && ny < map.length && map[nx][ny] != 1) {
                let ncost = 0;
                if (cur_dir == -1 || cur_dir == i) {
                    ncost = cur_cost + 100;
                } else if (cur_dir != i) {
                    ncost = cur_cost + 600;
                }

                if (map[nx][ny] == 0) {
                    map[nx][ny] = ncost;
                    q.push([nx, ny, ncost, i, map]);
                } else if (map[nx][ny] >= ncost) {
                    map[nx][ny] = ncost;
                    q.push([nx,ny,ncost,i]);
                }
            }
        }

    }
}
let board = [[0,0,0],[0,0,0],[0,0,0]];
console.log(solution(board));

bfs를 이용하여 구현하였다. 단순히 도착했을 때 비용구하는거 까진 했는데 통과는 하지못했었다.
그래서 다른 사람의 코드를 보며 다시풀어봤다.
bfs를 돌 때 x, y, 현재cost, 방향값, 지도를 가지고 돌았다.
dx, dy로 방향을 설정했다. 4방탐색을 하다가 조건을 만족하고, 현재의 dir이 i와 다르면 방향을 트는 것이니까 바뀔 cost에 600을 더하고 i면 같은 방향이니까 100을 더한다.

그 다음 이동할 곳인 map[nx][ny]가 0이면 이동할 곳에 바뀔 cost를 저장하고, q에 push한다.
만약 이동할 곳이 ncost보다 크다면 더 적은 ncost를 map에 저장하고, q에 push한다.
종료조건은 현재 x,y,가 map길이-1일때 answer에 지금 있는 answer와 현재cost를 비교해 더 작은 값을 저장한다.

📘 참고

https://codingjuny.tistory.com/41