<Medium> Pacific Atlantic Water Flow (LeetCode : C#)

https://leetcode.com/problems/pacific-atlantic-water-flow/

📕 문제 설명

낮거나 높은 height로 물이 흐를 수 있을 때 pacific ocean과 atlantic ocean 모두 도달 가능한 island position들 반환하기

• Input
  island height 정보 (int[][])
• Output
  pacific ocean과 atlantic ocean 모두 도달 가능한 island position 리스트

예제

풀이

모든 셀에 대해 dfs로 pacific, atlantic 닿을 수 있는지 확인하는 식으로 구현했다.

public class Solution {
    public IList<IList<int>> PacificAtlantic(int[][] heights) {
        List<IList<int>> answerList = new List<IList<int>>();
        int[] dirX = new int[4] {1, -1, 0, 0};
        int[] dirY = new int[4] {0, 0, 1, -1};
        bool isPacificTouched = false;
        bool isAtlanticTouched = false;

        for (int i = 0; i < heights.Length; i++)
        {
            for (int j = 0; j < heights[0].Length; j++)
            {
                isPacificTouched = false;
                isAtlanticTouched = false;
                DFS(i, j, new bool[heights.Length, heights[0].Length]);

                if (isPacificTouched && isAtlanticTouched)
                {
                    answerList.Add(new List<int>() {i, j});
                }
            }
        }

        return answerList;

        void DFS(int x, int y, bool[,] tempVisited)
        {
            // pacific touch 하는 경우 (top, left)
            if (x == 0 || y == 0) isPacificTouched = true;
            // atlantic touch 하는 경우 (bottom, right)
            if (x == (heights.Length - 1) || y == (heights[0].Length - 1)) isAtlanticTouched = true;
            // 둘다 touch 한 케이스면 dfs 종료
            if (isPacificTouched && isAtlanticTouched) return;
            if (tempVisited[x, y]) return;
            tempVisited[x, y] = true;

            for (int i = 0; i < 4; i++)
            {
                int newX = x + dirX[i];
                int newY = y + dirY[i];

                if (newX < 0 || newX >= heights.Length || newY < 0 || newY >= heights[0].Length) continue;
                // 현재 셀보다 더 높은 높이 만나면 패스
                if (heights[newX][newY] > heights[x][y]) continue; 
                DFS(newX, newY, tempVisited);
            }
        }

        
    }
}

결과