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

DFS와 BFS에 관련된 문제이다.

DFS는 전체를 경험하여 그 중 원하는 값을 포착하는 것

BFS는 경험하는 도중 원하는 값이 발견되면 바로 종료 가능

* 최단거리를 구할 때는 BFS다 !!

 

내 코드) 틀림!

function solution(maps) {
  answer = 0;
  let m = maps.length;
  let n = maps[0].length;
  function getAnswer(x, y, val, list) {
    while (y < m && x < n) {
      if (y === m - 1 && x === n - 1) {
        answer = answer > val ? val : answer;
      }
      if (x < n - 1 && list[y][x + 1] == 1) {
        list[y][x + 1] = 0;
        getAnswer(x + 1, y, val + 1, list);
      }
      if (x >= 1 && list[y][x - 1] == 1) {
        list[y][x - 1] = 0;
        getAnswer(x - 1, y, val + 1, list);
      }
      if (y < m - 1 && list[y + 1][x] == 1) {
        list[y + 1][x] = 0;
        getAnswer(x, y + 1, val + 1, list);
      }
      if (y >= 1 && list[y - 1][x] == 1) {
        list[y - 1][x] = 0;
        getAnswer(x, y - 1, val + 1, list);
      }
    }
  }
  getAnswer(0, 0, 0, maps);
  return answer === 0 ? -1 : answer;
}

내 코드의 오류)

모든 경로를 다 확인하고, 가장 길이가 짧았던 것을 선정하는 DFS방식으로 문제를 풀었기 때문에, 너무 많은 시간이 걸렸을 뿐 아니라, 코드 오류로 인하여 답안이 맞지 않았다.

 

 

 

다른 분들이 푸신 답안 코드이다.

function solution(maps) {
  var yLen = maps.length - 1;
  var xLen = maps[0].length - 1;

  var queue = [[0, 0]];

  var visited = Array.from(new Array(maps.length), () =>
    new Array(maps[0].length).fill(false)
  ); //false로 가득 찬 maps와 동일하게 생긴 list

  var result = 0;

  while (queue.length) {
    //queue가 0이 아닐 때까지 반복
    // 모두 방문했던 곳이면 자동으로 끝

    result++;
    var size = queue.length;
    for (var i = 0; i < size; i++) {
      var point = queue.shift(); //queue의 가장 앞에 것 꺼냄
      var curY = point[0];
      var curX = point[1];

      if (visited[curY][curX]) continue; // 방문했던 곳이면 넘어감

      maps[curY][curX] = 0; //방문할 곳 0으로 변경

      visited[curY][curX] = true; //방문했다고 표시

      if (curY === yLen && curX === xLen) return result; // 적진에 도착

      if (curY < yLen && maps[curY + 1][curX] === 1) //남쪽
        queue.push([curY + 1, curX]);
      if (curX < xLen && maps[curY][curX + 1] === 1)
        queue.push([curY, curX + 1]); //동쪽
      if (curY > 0 && maps[curY - 1][curX] === 1) // 서쪽
      queue.push([curY - 1, curX]);
      if (curX > 0 && maps[curY][curX - 1] === 1) //북쪽
      queue.push([curY, curX - 1]);
    }
  }

  return -1;
}

의문점)

queue가 빈 값이 될때까지 while문을 반복해야 한다.

모든 조건을 확인하고, 참이면 queue에 push 하면 결국 가장 긴 루트까지 확인해야 끝나는 것 아닌가라는 의문이 생겼다.

 

해결)

while문 반복 조건은 끝까지 확인했어도 적진(5,5)에 도착하지 못했을 경우를 대비한 것이다.

while문 속에 적진에 도착했을 때 return 하는 if문이 있기 때문에 가장 짧은 경우에서 중단될 수 있다.

 

갈래길이 나올 때, 오른쪽 그림이 왼쪽 그림보다 먼저 적진에 도착하고, 도착했을 때의 이동횟수를 return한다.

즉, 파란색 경로가 오른쪽 위에 있을 때, 빨간색 경로가 적진에 도달했기 때문에 해당 값이 return된다.