[Programmers] 게임 맵 최단거리 - JavaScript

Joosi_Cool·2023년 3월 14일
2

Programmers

목록 보기
41/98
post-thumbnail

설계 과정

우선 최단거리를 구하는 것이기 때문에 BFS를 이용하기로 했다.

  1. queue를 하나 만들고 0,0 초기값을 넣는다.
  2. 큐가 요소가 없어질때까지 아래과정 반복
    -> x,y = queue에서 뽑음
    이 뽑은 x,y에 앞,뒤,오른쪽,왼쪽을 움직이면서 아래를 체크한다.
    1) x,y가 좌표를 나가지 않는가?
    2) 지나갈 수 있는 길인가?
    -> 이를 통과하면 queue에 x,y를 넣고 지나간 것으로 벽으로 만듬.
  3. 이 행위들을 반복할때마다 count++를 해준다.
  4. 만약 이 행위를 반복하다 목표지점에 도달하면 ++count를 리턴


초기 코드

function solution(maps) {
    if(maps===[1]){return 1;}
    var queue = [[0,0]];
    var moveX = [-1,1,0,0];
    var moveY = [0,0,-1,1];
    var count =1;
    while(queue.length>0){
        var queLen = queue.length;
        for(var q = 0; q<queLen;q++){
            let [x,y] = queue.shift();
            for(var i =0;i<4;i++){
                var newX = x + moveX[i];
                var newY = y + moveY[i];
                if(newX===maps.length-1&&newY===maps[i].length-1) return ++count;
                if(newX>=0&&newY>=0&&newX<maps.length&&newY<maps[0].length&&maps[newX][newY]===1){
                    queue.push([newX,newY]);
                    maps[newX][newY] = 0;
                }
            }
        }
        count++;
    }
    
    return -1;
}


결과


특정 케이스에서 런타임에러, 시간 초과가 발생했다. 왜 이런걸까.... 뭐지



개선 코드

function solution(maps) {
    if(maps===[1]){return 1;}
    var visit = [];
    var queue = [[0,0]];
    var moveX = [-1,1,0,0];
    var moveY = [0,0,-1,1];
    var count =1;
    if(maps[maps.length - 1][maps[0].length - 2] === 0 && maps[maps.length - 2][maps[0].length - 1] === 0) return -1;
    while(queue.length>0){
        var queLen = queue.length;
        for(var q = 0; q<queLen;q++){
            let [x,y] = queue.shift();
            for(var i =0;i<4;i++){
                var newX = x + moveX[i];
                var newY = y + moveY[i];
                if(newX===maps[0].length-1&&newY===maps.length-1) return ++count;
                if(newX>=0&&newY>=0&&newX<maps[0].length&&newY<maps.length&&maps[newY][newX]===1){
                    queue.push([newX,newY]);
                    maps[newY][newX] = 0;
                }
            }
        }
        count++;
    }
    
    return -1;
}

결과

문제를 천천히 읽어보니 X,Y값에 대한 배치 문제가 있었다... 문제를 좀 더 집중력 있게 풀어야겠다...ㅠㅠ

profile
집돌이 FE개발자의 노트

2개의 댓글

comment-user-thumbnail
2023년 3월 14일

문제를 해결하기 위해 끈기있게 고민하시고 결국 푸셨군요! 멋지네요 👍

답글 달기
comment-user-thumbnail
2023년 3월 14일

문제를 정말 잘 푸시네요..
퍼가요~

답글 달기