200. Number of Island.md

Leetcode

200. Number of Island

문제링크

DFS, BFS

: 섬의 개수를 출력하는 문제

코드

class NumIslands {
    
    var grid = [[Character]]()
    
    func numIslands(_ grid: [[Character]]) -> Int {
        self.grid = grid
        var count = 0
        
        for row in 0..<grid.count {
            for column in 0..<grid[0].count {
                if self.grid[row][column] == "1" {
                    dfs(row, column)
                    count += 1
                }
            }
        }
        return count
    }
    
    func dfs(_ r: Int, _ c: Int) {
        if grid[r][c] == "0" { return }
        
        grid[r][c] = "0"
        if r-1 >= 0 { dfs(r-1, c) }
        if r+1 < grid.count { dfs(r+1, c) }
        if c-1 >= 0 { dfs(r, c-1) }
        if c+1 < grid[0].count { dfs(r, c+1) }
    }
    
    func bfs(_ r: Int, _ c: Int) {
        var queue : [(r: Int, c: Int)] = [(r: r, c:c)]
        self.grid[r][c] = "0"
        
        while !queue.isEmpty {
            let grid = queue.removeFirst()
            
            if grid.r-1 >= 0 && self.grid[grid.r-1][grid.c] == "1" {
                queue.append((r: grid.r-1, c: grid.c))
                self.grid[grid.r-1][grid.c] = "0"
            }
            if grid.r+1 < self.grid.count && self.grid[grid.r+1][grid.c] == "1" {
                queue.append((grid.r+1, grid.c))
                self.grid[grid.r+1][grid.c] = "0"
            }
            if grid.c-1 >= 0 && self.grid[grid.r][grid.c-1] == "1" {
                queue.append((grid.r, grid.c-1))
                self.grid[grid.r][grid.c-1] = "0"
            }
            if grid.c+1 < self.grid[0].count && self.grid[grid.r][grid.c+1] == "1" {
                queue.append((grid.r, grid.c+1))
                self.grid[grid.r][grid.c+1] = "0"
            }
        }
    }
}

풀이 설명

• bfs & dfs 둘 다 풀 수 있는 문제