Algorithm) BOJ) 백준 7576 - 섬의 개수

문제보러가기

1. 초기접근

문제 조건 해석

전형적인 dfs 문제로 단지번호붙이기 문제와 유사하다.

단, 이번에는 동서남북 + 대각선 까지 구해야 한다.

 

알고리즘

w, h 크기의 섬을 돌면서 dfs탐색을 한다.

섬의 개수만 구하면 되므로 처음 dfs를 시작할 때마다 count를 늘려준다.

2. 회고

전형적인 dfs문제였다. 머리속에 그려지는 문제는 빠르고 정확하게 풀 수 있도록 노력하자.

3. 코드

while let testCase = readLine()?.split(separator: " ") {
    
    let w = Int(testCase[0])!
    let h = Int(testCase[1])!
    
    if w == 0 && h == 0 {
        break
    }
    
    var map = [[String]](repeating: [String](), count: h)
    var visited = [[Bool]](repeating: [Bool](repeating: false, count: w), count: h)
    var count = 0
    
    let dr = [-1, -1, -1, 0, 0, 0, 1, 1, 1]
    let dc = [-1, 0, 1, -1, 0, 1, -1, 0, 1]
    
    for i in 0..<h {
        let lends = readLine()!.split(separator: " ").map({String($0)})
        
        for c in lends {
            map[i].append(c)
        }
    }
    
    func dfs(_ r: Int, _ c: Int) {
        if visited[r][c] {
            return
        }
        
        visited[r][c] = true
        
        if map[r][c] == "1" {
            for i in 0..<9 {
                let nr = r + dr[i]
                let nc = c + dc[i]
                
                if nr >= 0 && nc >= 0 && nr < h && nc < w {
                    dfs(nr, nc)
                }
            }
        }
    }
    
    for i in 0..<h {
        for j in 0..<w {
            if !visited[i][j] && map[i][j] == "1" {
                dfs(i, j)
                count += 1
            }
        }
    }
    
    print(count)
}