행렬_LeetCode_200. Number of island swift

https://leetcode.com/problems/number-of-islands/

Number of Islands - LeetCode

 

접근 방법

1. stack에 "1"인 좌표를 모두 저장, grid의 크기와 같은 방문여부Matrix init
2. stack의 마지막 요소를 가져와, 4방의 좌표를 확인, "1"인 경우 재귀탐색 및 방문여부Matrix에 해당 좌표 true
3. 1, 2 를 마쳤을 때, 섬의 갯수 += 1 
4. stack의 다음 요소를 가져와 1~3을 시행, 이 때 방문여부Matrix의 해당좌표가 true일 경우, 해당 요소 continue

정답 코드

class Solution {
    
    
    func numIslands(_ grid: [[Character]]) -> Int {
        var numOfIsland = 0
        var stack: [[Int]] = []
        var visited = [[Bool]].init(repeating: [Bool].init(repeating: false, count: grid[0].count), count: grid.count)
        
        func find(point: [Int]) -> Bool {
            
            if visited[point[0]][point[1]] == true {
                return true
            } else {
                visited[point[0]][point[1]] = true
            }
            
            let moves: [[Int]] = [[1,0], [-1,0], [0,1], [0,-1]]
            
            for move in moves {
                let temp1 = point[1] + move[1]
                let temp0 = point[0] + move[0]
                
                if temp1 < 0 || temp1 >= grid[0].count ||
                    temp0 < 0 || temp0 >= grid.count {
                    continue
                }
                
                if grid[temp0][temp1] == "1" {
                    find(point: [temp0,temp1])
                    visited[temp0][temp1] = true
                }
            }
            return false
        }
        
        for (i, row) in grid.enumerated() {
            for (ii, val) in row.enumerated() {
                if val == "1" {
                    stack.append([i,ii]) // this axis point is x,y reversed
                }
            }
        }
        
        while !stack.isEmpty {
            let point = stack.removeLast()
            
            if find(point: point) {
                continue
            }
            
            numOfIsland += 1
        }
        
        return numOfIsland
    }
}

성능

49 / 49 test cases passed.	Status:  Accepted
Runtime: 406 ms Memory Usage: 18.5 MB

아쉬운 점

방문 matrix와 stack을 사용하지 않고, 주어진 matrix를 순환하면서, 방문한 좌표를 0으로 바꿀 경우, 성능이 더 좋을 것을 확인 함.