[백준] (Swift) 4963번 - 섬의 개수 (DFS 풀이)

👉 문제링크

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

💻 문제풀이

• 가장 기본적인 DFS문제 (BFS도 가능)
• 그래프로 입력 받은 후, 1인 곳을 전부 탐색 → 탐색하면서 해당 위치 방문처리
• 방문처리 된 곳들을 돌아다니다가 방문처리할 곳이 없으면 count += 1
• 최종적으로 count 출력

 

💻 소스코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/4963_%EC%84%AC%EC%9D%98%EA%B0%9C%EC%88%98/main.swift

GitHub - deslog/Algorithm

let dx = [-1, 1, 0, 0, -1, -1, 1, 1]
let dy = [0, 0, -1, 1, -1, 1, -1, 1] //위 아 왼 오 왼쪽위 오른쪽위 왼쪽아래 오른쪽아래
while true {
    var count = 0
    let wh = readLine()!.split(separator: " ").map{ Int(String($0))! }
    
    if wh == [0, 0] {
        break
    }

    var islandMap: [[Int]] = []
    var visited = Array(repeating: Array(repeating: false, count: wh[0]), count: wh[1])

    for _ in 0..<wh[1] {
        islandMap.append(readLine()!.split(separator: " ").map { Int(String($0))! })
    }
    func dfs(_ x: Int, _ y: Int) {
        for i in 0..<dx.count {
            let nx = x + dx[i]
            let ny = y + dy[i]

            if nx < 0 || nx > wh[0]-1 || ny < 0 ||  ny > wh[1]-1 {
                continue
            } else {
                if !visited[nx][ny] && islandMap[nx][ny] == 1 {
                    visited[nx][ny] = true
                    dfs(ny, nx)
                }
            }
        }
    }

    // main
    for i in 0..<wh[1] {
        for j in 0..<wh[0] {
            if islandMap[i][j] == 1 && !visited[i][j] {
                visited[i][j] = true
                dfs(i, j)
                count += 1
            }
        }
    }
    print(count)
}