LeetCode 417 - Pacific Atlantic Water Flow (Medium)

문제

LeetCode - 417번

풀이 과정

입력으로 주어진 격자판에서 가장자리에 도달할 수 있는 좌표를 찾는 BFS 문제였습니다.

문제 조건에 따라 x 죄표 혹은 y 좌표 가 0보다 작아질 경우는 pacific 에 해당하고
그 반대의 경우에는 atlantic 에 해당합니다.

따라서 matrix 의 각 지점마다 BFS 를 수행하며 pacific 과 atlantic 에 모두 도달 가능한 경우에만
해당 죄표값을 기록하여 답을 구할 수 있습니다.

이때 인접한 지역에 대해서 값이 같거나 작을 경우에만 이동할 수 있다는 것에 유의하도록 합니다.

코드

/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var pacificAtlantic = function (matrix) {
  if (!matrix.length) return [];

  const M = matrix.length;
  const N = matrix[0].length;

  // 각 지점을 탐색해본다
  const ans = [];
  for (let x = 0; x < M; x++) {
    for (let y = 0; y < N; y++) {
      if (bfs(matrix, x, y, M, N)) {
        ans.push([x, y]);
      }
    }
  }

  return ans;
};

const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];

function bfs(matrix, x, y, M, N) {
  const q = [];
  const visit = new Array(M).fill(null).map((_) => new Array(N).fill(0));

  q.push([x, y]);
  visit[x][y] = 1;

  let pacific = false;
  let atlantic = false;

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

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

      // pacific, atlantic, in-cell
      if (nx < 0 || ny < 0) {
        pacific = true;
      } else if (nx >= M || ny >= N) {
        atlantic = true;
      } else if (!visit[nx][ny] && matrix[x][y] >= matrix[nx][ny]) {
        visit[nx][ny] = 1;
        q.push([nx, ny]);
      }
    }
  }

  return pacific && atlantic;
}