[JS | 알고리즘] BFS 와 0-1 BFS

기본 BFS

기본 BFS는 최단 거리를 고려해줄 때 알맞는 알고리즘이다.

1 ) 로직

• 표에서 움직일 수 있는 동서남북이 필요하다
  • 동서남북은 dx, dy 로 표현하게 된다.
  • 2차원 배열 [1][1]을 기준으로 남쪽은 [1+1][1] (=[2][1]) 이 되는 셈이다.

추천 문제 | 1687 숨바꼭질 5014 스타트링크 10026 적록색약

0-1 BFS

기존에 있는 BFS 보다 시간복잡도가 낮아서 잘 활용한다면, 유용하게 쓸 수 있다.

0-1 BFS는 가중치를 고민해주는 방법이다. 가중치가 낮은 것(0) 은 가중치가 높은 것(1) 보다 비용 없이 이동할 수 있으니 먼저 고려해주는 것이다.

1 ) 로직 ( Queue)

• 가중치가 낮은 것은 unshift
• 가중치가 높은 것은 push

추천 문제 | 1261 알고스팟

---

BFS 문제 풀이 업데이트 ✨

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

1. Queue(q)를 만들어준다.
2. 동서남북으로 이동할 수 있는 dx, dy를 만들어준다.
3. Q의 length 만큼 반복해준다. (Q의 length 가 1회 이동 이동을 의미한다.)
4. 동서남북으로 이동하면서, 조건이 맞는지 확인한다. ( 범위를 벗어나진 않았는지, 방문했던 적은 없는지, 움직일 수 있는 공간인지) 등

원래 방문 여부를 확인하는 2차원 배열 visited를 fill(false)로 채웠는데, 유효성 검사에서 걸린다. 그래서 fill(0)으로 채워주는 것이 안전하다. 

function solution(maps) {
  var answer = -1;

  const [n, m] = [maps.length, maps[0].length];
  const [dx, dy] = [
    [0, -1, 0, 1],
    [-1, 0, 1, 0],
  ];

  let q = [];
  const visited = Array.from(Array(n), () => Array(m).fill(0));

  q = [[0, 0]];
  visited[0][0] = 1;
  let L = 0;

  while (q.length) {
    const len = q.length;

    for (let i = 0; i < len; i++) {
      const [x, y] = q.shift();

      if (x + 1 === n && y + 1 === m) {
        return L + 1;
      }
      for (let j = 0; j < 4; j++) {
        const [tx, ty] = [x + dx[j], y + dy[j]];

        if (
          tx >= 0 &&
          tx < n &&
          ty >= 0 &&
          ty < m &&
          !visited[tx][ty] &&
          maps[tx][ty]
        ) {
          q.push([tx, ty]);
          visited[tx][ty] = 1;
        }
      }
    }
    L++;
  }

  return answer;
}