[Programmers]게임 맵 최단거리/JS

문제링크

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

프로그래머스

---

접근방법

처음엔 DFS?BFS? 뭐로 풀어야 할 지부터 고민했다.

그래서 개념부터 찾아봤더니 최단거리문제는 BFS로 풀어야한다해서 BFS 구현하고 

문제에서 원하는 조건 몇개만 추가해주면 되겠다라고 생각했다.(말이 쉽지..)

 

처음코드

function solution(maps) {
  var answer = 0;
  let visit = Array.from(new Array(maps.length), () =>
    new Array(maps[0].length).fill(false)
  );
  //순서대로 상우하좌(시계방향)
  let dx = [0, 1, 0, -1];
  let dy = [-1, 0, 1, 0];

  let q = [];
  q.push([0, 0]);
  visit[0][0] = true;

  while (q.length != 0) {
    let [x, y] = q.shift();

    for (let i = 0; i < 4; i++) {
      let nx = x + dx[i];
      let ny = y + dy[i];

      if (
        nx < 0 ||
        nx >= maps[0].length ||
        ny < 0 ||
        ny >= maps.length ||
        maps[nx][ny] == 0
      )
        continue;
      if (nx == maps[0].length - 1 && ny == maps.length - 1) {
        answer++;
        return answer;
      }
      if (!visit[nx][ny] && maps[nx][ny] == "1") {
        q.push([nx, ny]);
        visit[nx][ny] = true;
        answer++;
      }
    }
  }

  return answer;
}

visit[][] 배열을 만들어서 방문여부를 판단하고

배열 범위 벗어나거나 벽이 세워진 곳이면 continue;

도착지에 도착하면 answer+1 해주고 종료

조건에 만족하는 곳이면 큐에 넣고, 방문 처리해주고, answer+1

이렇게 코드를 짰는데 첫번째 testcase의 답이 11인데 자꾸 16이 나왔다ㅠㅠ

계속 코드 수정해보면서 풀었는데도 안풀림.. 몇시간동안..

이정도면 못 푸는 문제다 싶어서 구글링해서 참고했다.

 

구글링 해본 결과!

1. 1. visit 배열 만들 필요가 없다.
   방문한 경우, 주어진 maps 배열을 0(벽)으로 설정해주면 된다.
2. 2. 전부 방문 했는데 도착지에 도착을 못하면 도착할 수 없는 경우이다.
   이 경우를 어떻게 처리해야하는지 머리 아팠는데 간단한 것이였다..
   도착지에 도착하면 지금까지 방문한 횟수를 return 해주고
   아니라면 -1을 return 해주면 해결~

마지막으로 구글링해서 얻은 정보는 아닌데,

이 문제도 손으로 그려봤더니 내가 놓치고 있는 부분이 있었다.

x,y 좌표를 구해서 maps[x][y] -> 이렇게 풀고 있었는데

maps[y][x] 였다는 사실..ㅎ

이거 알고 절규함. 나는 정말 바보인가 싶었다..

결과코드

function solution(maps) {
  const rows = maps.length;
  const cols = maps[0].length;

  //순서대로 상우하좌(시계방향)
  const dx = [0, 1, 0, -1];
  const dy = [-1, 0, 1, 0];

  const queue = [];
  queue.push([0, 0, 1]);

  while (queue.length > 0) {
    const [x, y, distance] = queue.shift();

    //도착지점 도착
    if (x === cols - 1 && y === rows - 1) {
      return distance;
    }

    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];

      //좌표의 위치가 범위안에 있고, 벽이 없는 자리 일때(=1)
      if (nx >= 0 && nx < cols && ny >= 0 && ny < rows && maps[ny][nx] == 1) {
        queue.push([nx, ny, distance + 1]);
        maps[ny][nx] = 0;
      }
    }
  }
  //도착할 수 없는 경우
  return -1;
}

결과

 

사실 BFS의 개념이 완벽히 잡혀있었다면 쉽게 풀었을지도 모르는 문제이다.

알고리즘 개념 공부도 해야겠다는 생각이 들었다.

열심히 풀다보면 이런 문제 뚞딲 푸는 날이 오겠지~!