LeetCode - Pacific Atlantic Water Flow (Javascript)

문제 설명

높이가 자신 이하인 곳으로만 빗물이 흘러 내려갈 수 있다고 가정했을 때,
Pacific과 Atlantic 두 바다로 모두 물이 흘러들어갈 수 있도록 하는 섬의 좌표를 구하는 문제다.

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island’s left and top edges, and the Atlantic Ocean touches the island’s right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell’s height is less than or equal to the current cell’s height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Example 1:

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Example 2:

Input: heights = [[2,1],[1,2]]
Output: [[0,0],[0,1],[1,0],[1,1]]

Constraints:

• m == heights.length
• n == heights[r].length
• 1 <= m, n <= 200
• 0 <= heights[r][c] <= 105

---

소스코드

솔직히 많이 어려웠던 문제다…
생각해줘야 하는 조건들이 이전 문제들보다 많았어서 조금 애를 먹었다.

const pacificAtlantic = (heights) => {
  const answer = [];
  if (!heights.length) return [];
  const rowMax = heights.length - 1;
  const colMax = heights[0].length - 1;

  const pacific = new Array(rowMax + 1)
    .fill(0)
    .map((_) => new Array(colMax + 1).fill(0));
  const atlantic = new Array(rowMax + 1)
    .fill(0)
    .map((_) => new Array(colMax + 1).fill(0));

  const traverse = (row, col, visited, height) => {
    if (heights[row] === undefined || heights[row][col] === undefined) return;
    if (visited[row][col] || heights[row][col] < height) return;
    visited[row][col] = 1;
    traverse(row - 1, col, visited, heights[row][col]); // up
    traverse(row, col + 1, visited, heights[row][col]); // right
    traverse(row + 1, col, visited, heights[row][col]); // down
    traverse(row, col - 1, visited, heights[row][col]); // left
  };

  for (let row = 0; row <= rowMax; row++) {
    traverse(row, 0, pacific, -1);
    traverse(row, colMax, atlantic, -1);
  }

  for (let col = 0; col <= colMax; col++) {
    traverse(0, col, pacific, -1);
    traverse(rowMax, col, atlantic, -1);
  }

  for (let row = 0; row <= rowMax; row++) {
    for (let col = 0; col <= colMax; col++) {
      if (pacific[row][col] && atlantic[row][col]) answer.push([row, col]);
    }
  }
  return answer;
};

---

소스 코드 (의문점)

위 솔루션에서 사용한 매트릭스 방식이 아닌, 해시맵을 통한 풀이를 하다가 테스트케이스의 오류를 발견했다.

위와 같은 경우, [1,1] ~ [1,9] 는 pacific과 atlantic까지 물을 흘려 보낼 수 없다. 하지만, 48번 테스트 케이스에서는 [1,0]~[1,11]까지를 모두 정답으로 간주하고 있었다.

나의 output이 정답이라고 생각하는데… 왜 테스트케이스는 아래의 경우를 정답이라고 설정해뒀는지 이해가 되지 않는다.

이렇게 테스트 케이스를 다시 점검해보니… 1번 솔루션은 어떻게 통과가 된건지 모르겠다. 멘붕이다…

그래서 1번 소스코드에 위의 테스트케이스를 적용하여 console.log로 찍어보니, atlantic에도 [1,1]~[1,9]가 1로 체크돼있었다. 어찌된 영문인지 모르겠으나, 한 번 날을 잡고 array 파라미터와 object 파라미터에 차이가 있는지, 또는 템플릿 스트링 사용에 문제가 있었는지 등을 조사해봐야겠다.

해시맵을 사용한 소스코드는 아래와 같다.

const pacificAtlantic = (heights) => {
  const answer = [];
  if (!heights.length) return [];
  const rowMax = heights.length - 1;
  const colMax = heights[0].length - 1;
  const pacific = {};
  const atlantic = {};
  // pacific, atlantic의 방문여부 체크를 위한 해시맵 생성
  for (let i = 0; i <= rowMax; i++) {
    for (let j = 0; j <= colMax; j++) {
      pacific[`${i}${j}`] = 0;
      atlantic[`${i}${j}`] = 0;
    }
  }

  for (let row = 0; row <= rowMax; row++) {
    traverse(row, 0, -1, pacific);
    traverse(row, colMax, -1, atlantic);
  }
  for (let col = 0; col <= colMax; col++) {
    traverse(0, col, -1, pacific);
    traverse(rowMax, col, -1, atlantic);
  }
  function traverse(row, col, height, visited) {
    if (heights[row] === undefined || heights[row][col] === undefined) return;
    if (visited[`${row}${col}`] || height > heights[row][col]) return;
    visited[`${row}${col}`] = 1;
    traverse(row - 1, col, heights[row][col], visited); // up
    traverse(row, col + 1, heights[row][col], visited); // right
    traverse(row + 1, col, heights[row][col], visited); // down
    traverse(row, col - 1, heights[row][col], visited); // left
  }
  for (let i = 0; i <= rowMax; i++) {
    for (let j = 0; j <= colMax; j++) {
      if (pacific[`${i}${j}`] && atlantic[`${i}${j}`]) answer.push([i, j]);
    }
  }
  return answer;
};

---