[Swift] 백준 2667 단지번호붙이기 (Graph Traversal)

 

📌 풀이

💬 Code

import Foundation

let n = Int(readLine()!)!
var graph = [[Int]]()
var visited = [[Bool]]()
var result = [Int]()

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

for _ in 0..<n {
    let line = readLine()!.map { Int(String($0))! }
    graph.append(line)
    visited.append(Array<Bool>(repeating: false, count: n))
}

for i in 0..<n {
    for j in 0..<n {
        if graph[i][j] == 1 && !visited[i][j]{
            result.append(bfs(i, j))
        }
    }
}

print(result.count)
result.sort()
result.forEach{ print($0) }

func bfs(_ x: Int, _ y: Int) -> Int {
    var cnt = 0
    var queue = Array<[Int]>()
    queue.append([x, y])
    visited[x][y] = true

    while !queue.isEmpty {
        let now = queue.removeFirst()
        cnt += 1

        for i in 0..<4 {
            let nx = now[0] + dx[i]
            let ny = now[1] + dy[i]
            if 0..<n ~= nx && 0..<n ~= nx && graph[nx][ny] == 1 && !visited[nx][ny] {
                queue.append([nx, ny])
                visited[nx][ny] = true
            }
        }
    }

    return cnt
}

 

 

2667번: 단지번호붙이기