[알고리즘] 백준 - 미로탐색(자바스크립트)

백준 2178번 미로 탐색

그래프를 DFS나 BFS로 완전 탐색할 때 방문 여부를 체크하는 배열을 항상 따로 두었다. 그러나 문제를 풀 때마다 이중 배열을 하나 더 두는 것은 결국 메모리를 불필요하게 소모하는 일이 아닌지 생각했다. 또한, 실제 입사 코딩 테스트에서 변수 선언을 남발해서 로직을 수정하기 어려운 경우가 너무 많았다. 그래서 변수 선언을 줄이는 연습을 하기 위해 방문 여부를 체크하는 배열없이 문제를 해결해봤다.

 

이 문제 같은 경우에는 좌표 [0, 0]에서 좌표 [N, M]의 최소 거리를 찾는 것이다. 이런 경우에는 특정 좌표 [x, y]에 대해 이동한 거리를 지속적으로 등록하면 방문 여부를 체크하는 배열을 두지 않아도 될 것 같았다. 이동이 가능하나 방문하지 않은 좌표는 1로 두고, 방문한 좌표는 1 이상의 숫자로 두는 것이다.

// 입력 받아서 배열로 바꾸는 함수
const makeBoard = (arr) => {
  const board = [];

  for (let i = 0; i < arr.length; i++) {
    const tmp = [];
    for (let j = 0; j < arr[i].length; j++) {
      if (arr[i][j] === "1") {
        tmp.push(1);
      } else {
        tmp.push(0);
      }
    }

    board.push(tmp);
  }

  return board;
};

const bfs = (board, x, y) => {
  const queue = [];
  const dirs = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];

  queue.push([x, y]);

  while (queue.length > 0) {
  	// 현재 좌표 [cx, cy]
    const [cx, cy] = queue.shift();

    for (let [dx, dy] of dirs) {
      // 다음 좌표[nx, ny]
      const nx = cx + dx;
      const ny = cy + dy;

      if (nx >= 0 && nx < board.length && ny >= 0 && ny < board[0].length) {
        if (board[nx][ny] === 1) {
          board[nx][ny] = board[cx][cy] + 1;
          queue.push([nx, ny]);
        }
      }
    }
  }
};

const solution = (arr) => {
  const board = makeBoard(arr);

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      if (board[i][j] === 1) {
        bfs(board, i, j);
      }
    }
  }

  console.log(board[board.length - 1][board[0].length - 1]);
};

 

이중 배열 하나가 없으니 로직도 훨씬 깔끔하고 이해하기 편한 것 같다. 앞으로 BFS나 DFS를 사용할 때도 사용하는 변수를 최소화하는 습관을 필수적으로 길러야 할 것 같다.