[알고리즘] Swift -백준 #4963(섬의 개수)

 

문제링크

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

4963번: 섬의 개수

 

 

 

 

 

 

분석

섬의 개수를 세는 프로그램

 

 한 정사각형과 가로 세로 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다

 두 정사각형이 같은 섬에 있으려면 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야한다

 지도 밖으로 나갈 수 없다

 

 여러개의 테스트케이스로 이루어져있음

 너비w, 높이h

 둘째줄부터 h개 줄에는 지도 (1은 땅, 0은 바다)

 마지막 입력은 0 0

 

풀이

import Foundation

var result: [Int] = []
while true {
    let input = readLine()!.split(separator: " ").map { Int($0)!}
    if input == [0, 0] { break }
    let (w, h) = (input[0], input[1])
    var map: [[Int]] = []
    var check = Array(repeating: Array(repeating: false, count: w), count: h)
    for _ in 0..<h {
        map.append(readLine()!.split(separator: " ").map {Int($0)!})
    }

    let dx = [-1, 1, 0, 0, -1, -1, 1, 1]
    let dy = [0, 0, -1, 1, -1, 1, -1, 1]

    func isValid(y: Int, x: Int) -> Bool {
        return 0 <= y && y <= h-1 && 0 <= x && x <= w-1 ? true : false
    }

    func dfs(y: Int, x: Int) {
        check[y][x] = true

        for k in 0..<8 {
            let nextY = y + dy[k]
            let nextX = x + dx[k]
            
            if isValid(y: nextY, x: nextX) && !check[nextY][nextX] && map[nextY][nextX] == 1 {
                dfs(y: nextY, x: nextX)
            }
        }
    }

    var count = 0
    for y in 0..<h {
        for x in 0..<w {
            if map[y][x] == 1 && !check[y][x] {
                dfs(y: y, x: x)
                count += 1
            }
        }
    }
    result.append(count)
}

_ = result.map { print($0, terminator: "\n") }

 

결과

 

 

 

 

---

📂  정리

가로세로대각선(상하좌우대각선)의 인접한 영역을 구하는 문제