LeetCode알고리즘 Number of Islands문제

오늘은 200번 Number of Islands문제를 풀어보겠습니다.
난이도는 중간 난이도며 성공률은 49%로 꽤 높습니다.

문제는 아래와 같습니다.

m * n의 2차원 배열 grid이 주어지고 1은 땅이고 0은 물이며, 섬의 개수를 리턴해줘야 합니다.
아래와 같은 예시를 살펴보겠습니다.
1이 땅이고 0이 물이니 섬을 개수를 세기 위해서 1의 시작점을 봅니다.
1로만 이루어져 있고 0에 둘러싸여 있으면 섬이라고 생각하면 됩니다.

섬만 표시하다면 아래와 같이 3개의 섬이 있고 정답으로 3을 리턴해주면 됩니다.

코드를 살펴보겠습니다.
저는 전형적인 방법 DFS로 풀었습니다.

import Foundation

/// 200. Number of Islands

let xArr = [1,0,-1,0]
let yArr = [0,1,0,-1]

func numIslands(_ grid: [[Character]]) -> Int {
    var answer = 0
    var copy = grid
    var visited = Array(repeating: Array(repeating: false, count: grid.first!.count), count: grid.count)
    
    func dfs(grid: inout [[Character]], x: Int, y: Int) {
        visited[x][y] = true

        for i in 0..<4 {
            let myX = x + xArr[i]
            let myY = y + yArr[i]
            
            if myX >= 0 , myY >= 0, myX < grid.count, myY < grid.first!.count {
                if grid[myX][myY] == "1", visited[myX][myY] == false {
                    dfs(grid: &grid,x: myX,y: myY)
                }
            }
        }
    }
    
    for x in 0..<grid.count {
        for y in 0..<grid.first!.count {
            if copy[x][y] == "1", visited[x][y] == false {
                answer = answer + 1
                dfs(grid: &copy, x: x, y: y)
            }
        }
    }
    
    return answer
}

xArr, yArr배열은 4방향에 대한 x,y값을 배열에 넣은 값입니다.

먼저 이중 for문을 통해서 해당 지점이 1이고 방문하지 않았던 곳이라는 조건이 만족하면 
섬이 하나 있으니 answer + 1을 해주고 dfs함수를 돌립니다.

dfs함수로 grid를 카피한 copy라는 배열의 레퍼런스를 전달해줍니다.
grid의 수정은 없지만 call by reference를 활용하기 위해서 grid를 카피한 copy라는 배열을 만들어줬습니다. (inout)

dfs함수 내에서 방문했다는 표시를 해주고 위, 아래, 좌, 우로 확인해가며 1이 있고 방문하지 않은 조건에 만족하면 다시 dfs로 돌려줍니다.
이렇게 dfs를 쭉쭉 들어가는 과정이 확장하면서 섬을 찾아가는 과정입니다.

결과

resource:
leetcode.com/problems/number-of-islands/submissions/