[백준] 2667 단지번호붙이기

 

문제

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

입력

n = 지도의 크기 (가로 세로 크기)
board: [[Character]] = [] , "0"과 "1"로 구성됨 

board[i] = "0" = 집이 없는 곳
board[i] = "1" = 집이 있는 곳

5<= n <= 25

결과

ans: Int = 단지 수 

단진 내 집의 수를 오름차순으로 정렬 후 한줄 씩 출력

해석

2중 반복문을 돌며 집이 존재하고, 아직 방문한 적이 없다면 새로운 단지

 

이 때 dfs로 들어가면서 연결된 모든 집을 하나의 단지로 인식하고 방문하며 count하자.

 

코드

import Foundation

let n = Int(readLine()!)!

var board: [[Character]] = []

for _ in 0..<n {
    board.append(Array(readLine()!))
}

var visited: [[Bool]] = [[Bool]](repeating: [Bool](repeating: false, count: n), count: n)

var answer: [Int] = []

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

func dfs(_ x: Int,_ y: Int) -> Int {
    visited[x][y] = true
    
    var count: Int = 1
    
    for i in 0..<4 {
        let nx = x + dx[i]
        let ny = y + dy[i]
        
        if nx < 0 || nx >= n || ny < 0 || ny >= n { continue }
        
        if visited[nx][ny] || board[nx][ny] == "0" { continue }
        
        count += dfs(nx, ny)
        
    }
 
    return count
}


for i in 0..<n {
    for j in 0..<n {
        if board[i][j] == "1" && visited[i][j] == false {
            answer.append(dfs(i, j))
        }
    }
}

print(answer.count)
answer.sorted().forEach {
    print($0)
}