[Swift 알고리즘] 백준 BOJ - 4963 섬의 개수

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "백준 BOJ - 4963 섬의 개수" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

4963번: 섬의 개수

 

---

풀이

이번 문제는 그래프 탐색 문제입니다.

매번 dfs로 풀다보니 이번 문제는 bfs로 풀어봤습니다. 물론 dfs로도 풀 수 있습니다!

 

모든 원소에 대해 map[i][j]가 1이면 bfs 탐색을 시작합니다.

좌표를 저장하는 queue에 (i, j) 튜플을 넣어줍니다.

bfs는 큐를 이용해야 하므로 removeFirst()를 이용해 맨 첫 원소를 빼줍니다.

이후 상하좌우 대각선까지 총 8개의 원소를 참조하며 값이 1이면 queue에 넣어줍니다.

이 로직을 queue가 빌 때까지 반복해줍니다.

 

해당 bfs가 종료되면 섬 1개의 탐색을 완료한 것이므로 count를 1 증가시킵니다.

 

이번 문제에서는 visited 대신 map의 원소를 1에서 0으로 변경하는 것으로 진행을 해봤는데요.

이게 더 효율적이긴 합니다만... 솔직히 제 스타일은 visited를 선언해서 체크하는 것이 더 좋아요.

역할이 명확하잖아요!?

 

---

전체 코드

//4963 섬의 개수
import Foundation

var w = 0, h = 0
var maps: [[Int]] = [[Int]]()

let di = [1, 1, 0, -1, -1, -1, 0, 1]
let dj = [0, 1, 1, 1, 0, -1, -1, -1]
func bfs(_ i: Int, _ j: Int) {
    var queue: [(Int, Int)] = [(i, j)]
        
    while !queue.isEmpty {
        let node = queue.removeFirst()
        for i in 0..<8 {
            let (nx, ny) = (node.0 + di[i], node.1 + dj[i])
            if (0..<h).contains(nx) && (0..<w).contains(ny) {
                if maps[nx][ny] == 1 {
                    maps[nx][ny] = 0
                    queue.append((nx, ny))
                }
            }
        }
    }
}

while true {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    w = input[0]
    h = input[1]
    if w == 0 && h == 0 {
        break
    }
    
    maps = [[Int]]()
    
    for _ in 0..<h {
        let map: [Int] = readLine()!.split(separator: " ").map { Int(String($0))! }
        maps.append(map)
    }
    
    var result: Int = 0
    for i in 0..<h {
        for j in 0..<w {
            if maps[i][j] == 1 {
                result += 1
                bfs(i, j)
            }
        }
    }
    print(result)
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.