[백준] (Swift) 4963번 - 섬의 개수 (DFS, 재귀)

⚫️ 문제

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

4963번: 섬의 개수

 

⚫️ 나의 풀이

아니 이것은,,, 내가 이 문제를 풀기 전에 바로 정리했던 '음료수 얼려먹기' 예제와 같은 문제다.

https://github.com/HotCodeBreakers/CodingTest/discussions/25

[개념정리] DFS+BFS (혹시,,, 문제풀이 전에 이코테 책을 보시나요!?) · Discussion #25 · HotCodeBreakers/Codi

여기 링크 들어가면, 맨 아래 부분에 있는 [이코테 예제 - 1️⃣번] 과 동일하다는 것! 그래서 풀이과정을 생각하지 않고 바로 써내려갔다.

• 연결된 부분이 몇개인지 세어주는 것이고, 상하좌우 뿐만 아니라 오른쪽위아래와 왼쪽위아래도 방문해주어야하기 때문에 방향키를 8개로 추가했다.
• 모든 칸을 탐색해야하기 때문에 이중 for문을 이용해서 모든 노드를 들러줄 것이다.
• DFS는 일단, 1이기만 하면 섬이 존재하는 것이 되므로, if문을 들어가기만 하면 true를 출력하도록 해서 result에 값을 더해줄 수 있게 구성하면 된다.
• DFS 내부에서는 for문을 사용해서 8개의 방향 모두 살펴봐준뒤, 인접한 부분들도 dfs 함수에 넣어서 방문처리를 해주는 과정을 반복한다~ 그럼 연결된 모든 부분이 방문처리가 되면서 하나의 섬으로 연결되는 것

 

⚫️ 정답코드

import Foundation

// 상하좌우 왼쪽위 왼쪽아래 오른쪽위 오른쪽아래
let dx = [-1, 1, 0, 0, -1, 1, -1, 1]
let dy = [0, 0, -1, 1, -1, -1, 1, 1]

while true {
    let wh = readLine()!.split(separator: " ").map{ Int($0)! }

    if wh == [0, 0] {
        break
    }

    var islandMap = [[Int]]()
    for _ in 0..<wh[1] {
        islandMap.append(readLine()!.split(separator: " ").map{ Int($0)! })
    }

    // MARK: - DFS 함수
    func dfs(x: Int, y: Int) -> Bool {
        if x < 0 || x >= wh[1] || y < 0 || y >= wh[0] {
            return false
        }

        if islandMap[x][y] == 1 {
            islandMap[x][y] = 0
            for i in 0..<8 {
                let nx = x + dx[i]
                let ny = y + dy[i]
                dfs(x: nx, y: ny)
            }
            return true
        }
        return false
    }

    // MARK: - main
    var result = 0
    for i in 0..<wh[1] {
        for j in 0..<wh[0] {
            if dfs(x: i, y: j) {
                result += 1
            }
        }
    }
    print(result)
}