알고리즘 - 게임 맵 최단거리

문제

• 링크

코드

function solution(maps) {
    var answer = 0;
    
    let dr = [-1,1,0,0];
    let dc = [0,0,-1,1];
    let min = Number.MAX_VALUE;
    const bfs = (graph, r,c, visited) => {
        const queue = [[r,c]];
    
        visited[r][c] = true;
        
        while(queue.length !== 0){
            const node = queue.shift();
        
            //console.log(node);
            
            if(node[0] === maps.length-1 && node[1] === maps[0].length-1){
                if(min > visited[node[0]][node[1]]){
                    min = visited[node[0]][node[1]];
                }
            }
            
            for(let i = 0; i < 4 ; i++){
                let nr = node[0] + dr[i];
                let nc = node[1] + dc[i];
                
                if(nr >= 0 && nr < maps.length && nc >= 0 && nc < maps[0].length){
                    if(graph[nr][nc] === 1){
                        
                        if(visited[nr][nc] !== 0){
                            if(visited[node[0]][node[1]]+1 < visited[nr][nc]){
                                queue.push([nr,nc]);
                                visited[nr][nc] = visited[node[0]][node[1]]+1;
                            }
                        }
                        else {
                            queue.push([nr,nc]);
                            visited[nr][nc] = visited[node[0]][node[1]]+1;
                        }
                        
                    }
                }
            }         
        }
        if(min === Number.MAX_VALUE){
            return -1;
        }
        else {
            return min;
        }
        
    }
    
    const visited2=[];
    
    for(let i = 0; i < maps.length ; i++){
        let test = [];
        for(let j = 0; j < maps[0].length ; j++){
            test.push(0);
        }
        visited2.push(test);
    }
    
    answer = bfs(maps, 0, 0, visited2);
    
    return answer;
}

회고

• bfs, 도착할 지점에 방문했는지 아닌지를 배열을 통해 표현

• 이미 방문했다면 0이 아닌 다른 값이 와 있을 것

  • 그 지점에 방문한 적이 있다면, 그 지점과 지금까지 온 거리의 최소값을 비교해서 최소값을 넣어준다.