[LeetCode] 417. Pacific Atlantic Water Flow

😎풀이

1. 깊이 우선 탐색을 통해 태평양, 대서양으로부터 특정 좌표까지 도달이 가능한지 역방향 탐색
2. 가장 끝 상, 하, 좌, 우를 기준으로 깊이 우선 탐색을 실시하여 도달 가능한 좌표 기록
3. 2중 순회를 통해 모든 좌표를 탐색하여 태평양과 대서양에서 모두 접근 가능한 지점의 좌표라면, 정답 배열에 추가
4. 정답 배열 반환

function pacificAtlantic(heights: number[][]): number[][] {
    const rows = heights.length
    const cols = heights[0].length
    const pacificVisit = new Set<string>()
    const atlanticVisit = new Set<string>()
    function dfs(row: number, col: number, visit: Set<string>, prevHeight: number) {
        const outOfBoundary = row < 0 || col < 0 || row >= rows || col >= cols
        if(outOfBoundary) return
        const curKey = `${row},${col}`
        const alreadyVisit = visit.has(curKey)
        const curHeight = heights[row][col]
        const lowHeight = heights[row][col] < prevHeight
        if(alreadyVisit || lowHeight) return
        visit.add(curKey)
        dfs(row - 1, col, visit, curHeight)
        dfs(row + 1, col, visit, curHeight)
        dfs(row, col - 1, visit, curHeight)
        dfs(row, col + 1, visit, curHeight)
    }
    for(let col = 0; col < cols; col++) {
        dfs(0, col, pacificVisit, 0)
        dfs(rows - 1, col, atlanticVisit, 0)
    }
    for(let row = 0; row < rows; row++) {
        dfs(row, 0, pacificVisit, 0)
        dfs(row, cols - 1, atlanticVisit, 0)
    }
    const result = []
    for(let row = 0; row < rows; row++) {
        for(let col = 0; col < cols; col++) {
            const curKey = `${row},${col}`
            if(!pacificVisit.has(curKey) || !atlanticVisit.has(curKey)) continue
            result.push([row, col])
        }
    }
    return result
};