[leetcode] Number of islands(DFS/BFS)

문제링크

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

대표적인 DFS/BFS 문제입니다.
예전에 풀었었지만 오랜 기간동안 알고리즘을 하지 않았기 때문에 까먹어서 감을 잡으려고 다시 풀어봤습니다.

DFS 풀이

class Solution {
    func numIslands(_ grid: [[Character]]) -> Int {
        var count = 0
        let row = grid.count
        let col = grid[0].count
        // 방문을 확인하기 위한 배열 생성
        var visited = Array(repeating: Array(repeating: false, count: col), count: row)
        // 상하 좌우로 움직일 수 있게 설정한 dx,dy
         let dx = [-1, 1, 0, 0]
            let dy = [0, 0, -1 , 1]

        func dfs(_ x: Int, _ y: Int) {
            visited[x][y] = true
			// 상하좌우로 움직임
            for i in 0..<4 {
                let next_x = x + dx[i]
                let next_y = y + dy[i]
				// 조건들을 만족하면 그 배열로 이동
                if next_x >= 0 && next_y >= 0 && next_x < row && next_y < col && !visited[next_x][next_y] && grid[next_x][next_y] == "1" {
                    dfs(next_x, next_y)
                }
            }
        }

        for i in 0..<row {
            for j in 0..<col {
                if !visited[i][j] && grid[i][j] == "1" {
                    dfs(i,j)
                    // dfs 함수를 종료하고 나오면 count에 +1 -> 섬이 하나 있다는 뜻
                    count += 1
                }
            }
        }

        return count
    }
}

BFS 풀이

class Solution {
    func numIslands(_ grid: [[Character]]) -> Int {
        var count = 0

        let row = grid.count
        let col = grid[0].count
        var visited = Array(repeating: Array(repeating: false, count: col), count: row)
        let dx = [-1,1,0,0]
        let dy = [0,0,-1,1]

        
        func bfs (_ x: Int, _ y: Int) {
            visited[x][y] = true
            // 방문할 곳을 저장해 놓는 queue 생성
            var queue = [(x,y)]
			// queue가 비기전까지 계속 반복
            while !queue.isEmpty {
            	// 현재 방문하고 있는 위치 x,y를 가져오고
                let cur_x = queue[0].0
                let cur_y = queue[0].1
                
                // 큐에서 현재 위치 삭제
                queue.removeFirst()

				// 현재 위치의 상하좌우 확인
                for i in 0..<4 {
                    let next_x = cur_x + dx[i]
                    let next_y = cur_y + dy[i]
					// 조건에 맞으면 방문표기
                    if next_x >= 0 && next_y >= 0 && next_x < row && next_y < col && !visited[next_x][next_y] && grid[next_x][next_y] == "1" {
                        visited[next_x][next_y] = true
                        queue.append((next_x, next_y))
                    }
                }
            }
        }
        for i in 0..<row {
            for j in 0..<col {
                if grid[i][j] == "1" && !visited[i][j] {
                    bfs(i, j)
                    count += 1
                }
            }
        }
        return count
    }
}

회고

• 기본적인 문제여서 한 번 개념을 다시 이해하고 푸니까 풀렸다
• 이런 느낌의 코드를 응용할 수 있도록 계속 연습해야겠다