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

문제

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

문제 풀이

코드1(DFS/정확성 100, 효율성 0)

function solution(maps) {
    let answer=0, cnt=1;
    const tmp=[];
    let dx=[-1, 0, 1, 0];
    let dy=[0, 1, 0, -1];
    
    function DFS(x, y){
        if(x===maps.length-1 && y===maps[0].length-1){
            answer++; //도착 
            tmp.push(cnt);
          	//cnt=1 하면 안됨!
        }
        else{
            for(let k=0; k<4; k++){
                let nx=x+dx[k];
                let ny=y+dy[k];
                if(nx>=0 && nx<=maps.length-1 && ny>=0 && ny<=maps[0].length-1 && maps[nx][ny]===1){
                    maps[nx][ny]=0;
                    cnt++;
                    DFS(nx, ny);
                    maps[nx][ny]=1;
                    cnt--;
                }
            }
        }
    }
    maps[0][0]=0; 
    DFS(0, 0);
    return (answer>0)? Math.min(...tmp):-1;
}

미로찾기 문제를 참고해서 DFS로 풀이했다.
정확성은 100이였지만, 효율성이 0이여서 69.9점밖에 받지 못했다.
이 문제는 '최단거리'를 푸는 문제기 때문에, BFS를 사용해야한다!

코드2(BFS)

function solution(maps) {
  // 남서북동 순서
  const dy = [1, 0, -1, 0];
  const dx = [0, -1, 0, 1];
  const row = maps.length; // 행
  const col = maps[0].length; // 열
  const visitCount = [...maps].map((r) => r.map((c) => 1));

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

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

      if (ny >= 0 && nx >= 0 && ny < row && nx < col) {
        if (maps[ny][nx] === 1 && visitCount[ny][nx] === 1) {
          visitCount[ny][nx] = visitCount[y][x] + 1;
          queue.push([ny, nx]);
        }
      }
    }
  }

  return visitCount[row - 1][col - 1] === 1 ? -1 : visitCount[row - 1][col - 1];
}

이분의 코드가 잘 정리되어서 가져왔다. BFS를 공부한 후, 다시 풀어보자!

참고

• https://velog.io/@rladpwl0512/9-4-%EB%AF%B8%EB%A1%9C%ED%83%90%EC%83%89DFS (DFS 문제)