문제
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
Constraints:
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 300
- grid[i][j] is '0' or '1'.
풀이
나의 풀이법
풀이 접근 과정
문제만 보면 전형적인 DFS 문제이다.
그런데 visited graph를 어떤 기준으로 잡아야할지 감이 오지 않았다.
그래서 나는 논리적으로 dfs를 사용하지 않고 풀기로 했다.
앞줄 정보와 바로 앞의 정보를 비교하여 섬을 모두 넘버링하기로 하였다.
넘버링하는 과정에서 섬 번호가 중복될 경우 하나의 섬은 파기하여야 하므로 최상위 섬 번호를 저장할 map도 만들었다.
정말 많은 시행착오 끝에 성공한 소스는 아래와 같다.
최종 소스코드는 많은 시행착오를 겪었지만 최초 소스코드와 크게 다르지 않다.
오히려 생각이 간단해지면서 코드도 간결해진 느낌이다.
최종 소스코드
class Solution {
fun numIslands(grid: Array<CharArray>): Int {
val m = grid.size
val n = grid[0].size
val island: Array<IntArray> = Array(m) { IntArray(n) { 0 } } // 현재 island 번호
val map = mutableMapOf<Int, Int>() // 최상위 island 번호
var cnt = 0
for (i in 0 until m) {
for (j in 0 until n) {
if (grid[i][j] == '1') {
val topIslandNum = if (i > 0 && map[island[i-1][j]] != null) map[island[i-1][j]]!! else 0
val leftIslandNum = if (j > 0 && map[island[i][j-1]] != null) map[island[i][j-1]]!! else 0
val parentNum =
if (topIslandNum != 0) topIslandNum
else if (leftIslandNum != 0) leftIslandNum
else ++cnt
island[i][j] = parentNum
map[island[i][j]] = parentNum
if (leftIslandNum != 0 && leftIslandNum != parentNum) {
map.forEach { if (it.value == leftIslandNum) map[it.key] = parentNum }
}
}
}
}
return map.filter { it.key == it.value }.size
}
}
현재 위치의 섬 번호를 저장할 island와 라벨링 된 섬 번호마다 부모 섬을 저장할 map을 선언하고 생성되는 섬의 개수를 저장할 변수 cnt를 선언한다.
(라벨링된 섬은 언제든 부모 섬으로 교체될 수 있다.)
입력받은 grid를 이중 for문을 이용하여 순회하고, 값이 땅(1)인 경우에만 아래와 같이 계산한다.
현재 나의 앞줄 정보[i-1][j]가 존재하고, 그 값이 땅인 경우 앞줄 땅의 섬 번호를 topIslandNum에 저장한다.
또한 현재 나의 앞 정보[i][j-1]가 존재하고, 그 값이 땅인경우 앞 땅의 섬 번호를 leftIslandNum에 저장한다.
섬 번호의 우선순위는 topIslandNum으로 한다.
topIslandNum이 0이 아니면 최상위 섬 번호인 parentNum는 topIslandNum이 된다.
이 경우에 leftIslandNum이 0이 아닌 경우 leftIslandNum의 최상위 부모 섬 번호는 topIslandNum가 되며, leftIslandNum을 부모로 갖는 값 모두 부모가 topIslandNum로 변경된다.
만약 topIslandNum이 0이고, leftIslandNum이 0이 아니면 parentNum는 leftIslandNum이 된다.
topIslandNum와 leftIslandNum가 모두 0이면 parentNum는 누적된 섬 번호의 +1을 한 값이 된다.
현재 섬 정보와 현재 섬의 부모 값에 parentNum을 넣어준다.
for문이 종료된 후 map에서 key값과 value 값(즉, 자기 자신을 부모로 갖는 섬)의 개수를 리턴해준다.
다른 풀이
하지만 이 문제의 정석 풀이는 바로 DFS를 이용해서 푸는 것이다.
나는 Map을 한번 더 탐색해야 하는 번거로움이 있는데, 아래 풀이는 각 섬을 한번씩만 탐색하면 된다는 장점이 있다.
오늘도 새로운 접근법을 배웠다. (지식+1 !!)
class Solution {
fun numIslands(grid: Array<CharArray>): Int {
val m = grid.size
val n = grid[0].size
var count = 0
fun dfs(i: Int, j: Int) {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') return
grid[i][j] = '0' // Mark as visited
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
}
for (i in 0 until m) {
for (j in 0 until n) {
if (grid[i][j] == '1') {
count++
dfs(i, j) // 내 주변에 연결된 섬을 다 없애버리기!
}
}
}
return count
}
}
이 코드는 Depth-First Search (DFS) 알고리즘을 사용하여 육지를 발견하면 해당 육지와 연결된 모든 육지를 탐색하고, 섬의 개수를 증가시키는 방식으로 동작한다.
각 육지를 방문할 때마다 그 위치를 '0'으로 표시하여 중복 방문을 방지합니다. 그리고 모든 육지를 탐색한 후에 섬의 개수를 반환한다.
Comment
DFS로 접근하는 것이 너무 까다로웠다.
그래서 그냥 다 풀어서 쓰자고 결론을 내리고 그 코드를 작성하는 데는 그리 오랜 시간이 걸리지 않았다.
그러나 예외 사항이 많아지며 생각이 점점 복잡해지고 코드도 복잡해지고.
결국 하나가 해결되면 하나가 실패하는 악순환이 반복되었다.
그 날은 깔끔하게 접고 다른 날 다시 처음부터 생각을 이어갔다.
그랬더니 생각도 간결해지고 코드도 간결해진 것 같아 마음에 든다.
'LeetCode > Kotlin | Medium' 카테고리의 다른 글
[LeetCode/Kotlin]Medium - 36. Valid Sudoku (0) | 2023.08.27 |
---|---|
[LeetCode/Kotlin]Medium - 53. Maximum Subarray (0) | 2023.08.03 |
[LeetCode/Kotlin]Medium - 926. Flip String to Monotone Increasing (0) | 2023.07.16 |
[LeetCode/Kotlin]Medium - 17. Letter Combinations of a Phone Number (0) | 2023.07.16 |
[LeetCode/Kotlin]Medium - 22. Generate Parentheses (0) | 2023.07.07 |