[프로그래머스] 게임 맵 최단거리

처리조건

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

풀이

시작점은 배열의 제일 왼쪽 위에 있게되며 0,0이 된다. 그리고 상대팀 진영은 배열의 갖아 오른쪽 아래 이므로 [maps.length - 1, maps[0].length - 1]이 된다. 나는 0,0 기준으로 위 아래 왼쪽 오른쪽을 검사하여 1인 좌표들을 배열로 담고 해당 배열안에서 상대팀진영의 위치와 거리를 계산하여 가장  짧은 좌표를 다시 기준좌표로 바꿔주면서 이전의 기준점은 한번 거쳐 온 것을 표시하기위해 2로 바꾸어주었고 기준점 좌표와 상대방진영 좌표가 같아지면 break하도록 로직을 구현했다. 2로 바꿔줄 때마다 count를 올리며 만약에 기준점을 기준으로 위 아래 왼쪽 오른쪽 을 검사해도 찾을 좌표가 없다면 사실 상대방 진영으로 갈 방법이 없는 것이므로 count에 -1를 주고 break해버린다.

 

처음 짠 로직은 아래와 같다.

function solution(maps) {
  let boss = [maps.length - 1, maps[0].length - 1];
  startX = 0;
  startY = 0;
  let count = 0;

  while (true) {
    if (startX === maps.length - 1 && startY === maps[0].length - 1) {
      maps[startX][startY] = 2;
      count += 1;
      break;
    }
    console.log(maps);
    let impArr = [];
    if (startY - 1 >= 0 && maps[startX][startY - 1] === 1) {
      impArr.push([startX, startY - 1]);
    }
    if (startX - 1 >= 0 && maps[startX - 1][startY] === 1) {
      impArr.push([startX - 1, startY]);
    }
    if (startY + 1 <= maps[0].length - 1 && maps[startX][startY + 1] === 1) {
      impArr.push([startX, startY + 1]);
    }
    if (startX + 1 <= maps.length - 1 && maps[startX + 1][startY] === 1) {
      impArr.push([startX + 1, startY]);
    }

    if (impArr.length === 0) {
      count = -1;
      break;
    }

    let distunses = [];

    for (let i = 0; i < impArr.length; i++) {
      distunses.push({ XY: impArr[i], dis: calc(boss, impArr[i]) });
    }

    distunses.sort(function (a, b) {
      return a.dis - b.dis;
    });

    maps[startX][startY] = 2;
    count += 1;
    startX = distunses[0].XY[0];
    startY = distunses[0].XY[1];
  }
  console.log(maps);
  console.log(count);
}

function calc(boss, impXY) {
  const distuns = Math.abs(impXY[0] - boss[0]) + Math.abs(impXY[1] - boss[1]);

  return distuns;
}
solution([[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]);

 

작동하고 나서 maps를 확인해보면 아래처럼 잘 변경 되었다. 하지만 프로그래머스에서 테스트를 하면 7,9,11,13 통과가 안되고 효율성에서도 당연 문제가 생긴다.. 뭐가 문제인지 찾아보고 있다..

 

 

다른 풀이

function solution(s) {
    const dx = [0,0,1,-1];
    const dy = [1,-1,0,0];
    const queue = [[0,0,1]];

    while ( queue.length ) {
        const cur = queue.shift();
        if ( cur[0] === maps.length - 1 && cur[1] === maps[0].length - 1) 
            return cur[2]
        for(let i=0;i<4;i+=1){
            const yy = cur[0] + dy[i]
            const xx = cur[1] + dx[i]
            if(xx >= 0 && yy >= 0 && xx < maps[0].length && yy < maps.length && maps[yy][xx] === 1 ) {
                maps[yy][xx] = 0;
                queue.push([yy, xx, cur[2] + 1]);    
            }
        }
    }
    return -1
}