개발야옹

[Programmers] 깊이/너비 우선 탐색(DFS/BFS) lv2 - 게임 맵 최단거리 본문

Algorithm\CodingTest/Programmers

[Programmers] 깊이/너비 우선 탐색(DFS/BFS) lv2 - 게임 맵 최단거리

kitez 2023. 3. 17. 09:27

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

function solution(maps) {
    var answer = 0;
    // 상 하 좌 우
    const vector = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    
    const bfs = () => {
        const queue = [[0,0]];
        
        while(queue.length) {
            const cur = queue.shift();            
            if(maps[cur[0]][cur[1]] !== 0) {
                const vectors = [];
                
                vector.forEach((v) => {
                    const x = Number(cur[0])+ Number(v[0]);
                    const y = Number(cur[1])+ Number(v[1]);
                    
                    if(x >= 0 && y >= 0 && x < maps.length && y < maps[0].length && maps[x][y] === 1) {
                        vectors.push([x,y]);
                    }
                });
                
                const prev = maps[cur[0]][cur[1]];
                
                vectors.forEach((v) => {
                    maps[v[0]][v[1]] = prev+1;
                });
                queue.push(...vectors);
            }
        }
    }
    
    bfs();
    return maps[maps.length-1][maps[0].length-1] === 1 ? -1 : maps[maps.length-1][maps[0].length-1];
}
728x90