Pacific Atlantic Water Flow - LeetCode

Problem

  1. input: matrix의 높이 정보가 담긴 이차행렬 heights
  2. output: 비가 왔을 때, Pacific Ocean, Atlantic Ocean 모두로 흘러갈 수 있는 지역 리스트로 리턴
  3. 물은 높이가 같거나 더 낮은 지역으로만 흐를 수 있음

Untitled

Idea

처음 문제를 풀 때, 한번의 탐색으로 양쪽 바다에 이어지는 지를 한번에 체크하려다 풀이가 산으로 갔다. 알아서 더 어렵게, 힘들게 풀려했다.. (visited 설정이 힘들 뿐만 아니라, 기준이 두개(Pacific, Atlantic에 도달)이므로 탐색 순서에 따라 결과가 달라지는 좌표가 발생하기 때문)

각 바다와 맞닿아 있는 지역을 시작으로 DFS탐색을 두번 실행 후, 겹치는 탐색 지역을 리턴하면 되는 문제다 → Sol1

Solution

  1. DFS

    Pacific과 맞닿아 있는 지역을 시작으로 물이 흐를 수 있는 지역 DFS 탐색

    Atlantic과 맞닿아 있는 지역을 시작으로 물이 흐를 수 있는 지역 DFS 탐색

    두 바다로 모두 흐를 수 있는 지역 리턴

    class Solution {
    var m = 0
    var n = 0
    var visited = arrayOf(arrayOf(booleanArrayOf()))
    var heights = arrayOf(intArrayOf())
    val answer = mutableSetOf<List<Int>>()
    val answerVisited = hashMapOf<String, Boolean>()
    fun pacificAtlantic(heights: Array<IntArray>): List<List<Int>> {
        this.heights = heights
        m = heights.size
        n = heights[0].size
        visited = Array(m) { Array(n) { BooleanArray(2){ false } } }
				// Pacific과 맞닿아 있는 지역 시작
        for (i in 0 until m) dfs(i, 0, 0)
        for (i in 1 until n) dfs(0, i, 0)
				// Atlantic과 맞닿아 있는 지역 시작
        for (i in 0 until m) dfs(i, n - 1, 1)
        for (i in 0 until n - 1) dfs(m -1, i, 1)
        return answer.toList()
    }

    fun dfs(i: Int, j: Int, idx: Int) {
        visited[i][j][idx] = true
        if (idx == 1 && visited[i][j][0] && visited[i][j][1]) {
						// 탐색한 지역이 두 바다와 모두 연결되는 경우
            answer.add(listOf(i, j))
        }
        val moves = listOf(listOf(1, 0), listOf(-1, 0), listOf(0, 1), listOf(0, -1))
        for (move in moves) { // 상하좌우중 물이 흐를 수 있는 지역 DFS 탐색
            val (x, y) = i + move[0] to j + move[1]
            if (x in 0 until m && y in 0 until n && heights[x][y] >= heights[i][j] && !visited[x][y][idx]) {
                dfs(x, y, idx)
            }
        }
    }
}

    시간 복잡도: 배열 탐색 = n^2

    Untitled

Point

  1. DFS/BFS 탐색을 할 때, 기준을 한가지로 정하고 부합하는 경우만 탐색해야 됨