4963번: 섬의 개수

문제 풀이 아이디어

연결된 요소를 모두 찾아야 하는 전형적인 dfs 문제입니다.

주어진 조건에 의하면 8방향으로 이동할 수 있는 연결된 땅은 모두 하나의 섬으로 칩니다. 지도를 완전탐색하면서 땅이 나올 때마다 dfs를 통해서 연결된 땅을 모두 탐색해서 섬을 찾으면 됩니다.

코드

// 동서남북 + 대각선: 8방향 탐색
let dr = [1, -1, 0, 0, 1, 1, -1, -1]
let dc = [0, 0, 1, -1, 1, -1, 1, -1]

// 섬의 갯수를 세는 함수
func countIsland(w: Int, h: Int) {
    // 현재 좌표가 dfs의 대상인지 알아보는 함수
    func isValid(_ r: Int, _ c: Int) -> Bool {
        r >= 0 && r < h && c >= 0 && c < w && check[r][c] == false && matrix[r][c] == 1
    }
    
    // 8방향 dfs
    func dfs(_ r: Int, _ c: Int) {
        for i in 0..<8 {
            let nr = r + dr[i]
            let nc = c + dc[i]
            if isValid(nr, nc) {
                check[nr][nc] = true
                dfs(nr, nc)
            }
        }
    }
    
    // 지도 저장용 2차원 배열
    var matrix = [[Int]]()
    // 방문체크
    var check = Array(repeating: Array(repeating: false, count: w), count: h)
    // 섬의 갯수 세기
    var cnt = 0
    
    // matrix 입력 받기
    for _ in 0..<h {
        matrix.append(readLine()!.split(separator: " ").map { Int(String($0))! })
    }
    
    // matrix 내의 모든 점을 순회하면서 (땅 + 아직 미방문)이라면 거기 연결된 땅 모두 탐색
    for r in 0..<h {
        for c in 0..<w {
            if matrix[r][c] == 1 && check[r][c] == false {
                dfs(r, c)
                cnt += 1
            }
        }
    }
    
    print(cnt)
}

while true {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    let w = input[0], h = input[1]
    if w == 0 && h == 0 { break }

    countIsland(w: w, h: h)
}