Mac Plus

Hello Swift

백준 단지번호붙이기(2667)

  • 문제해설
  • DFS문제 (0,0) ~ (n,n)까지 돌면서 단지수르 구하고 단지수에 포함되는 아파트 수르 구하라.
  • 처음에 보고 막막한 상태에서 여러 코드들을 보면서 진행하였음
  • 쉽게 풀자면 맨 처음 1값이 나온다면 그 (n,n) 좌표를 가지고 1이 안나올때까지 재귀함수를 돌려가면서 그 상하좌우값을 계속 비교하는 것이다.
import Foundation

let n = Int(readLine()!)!
var groupId = 0
var dx: [Int] = [-1, 0, 1, 0] // 만약 (0,1)이 아파트라면 그 주위 동서남북에 있는 아파트들으 체크하기 위해서 사용
var dy: [Int] = [0, 1, 0, -1]
var arr: [[String]] = Array(repeating: Array(repeating: "", count: n), count: n)
var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: n), count: n)
var groups: [Int] = Array(repeating: 0, count: 25)
var result: [Int] = []

func dfsRecursion(_ x: Int, _ y: Int) {
    visited[x][y] = true
    groups[groupId] += 1
    
    for i in 0..<4 {
        let nx = x + dx[i]
        let ny = y + dy[i]
        
        if  0 <= nx && nx < n && 0 <= ny && ny < n {
            if Int(arr[nx][ny])! == 1 && visited[nx][ny] == false {
                dfsRecursion(nx, ny)
            }
        }
    }
}

for i in 0..<n {
    let strArr = Array(readLine()!)
    for j in 0..<strArr.count {
        arr[i][j] = String(strArr[j])
    }
}

for i in 0..<n {
    for j in 0..<n {
        if Int(arr[i][j])! == 1 && visited[i][j] == false {
            
            groupId += 1
            dfsRecursion(i, j)
        }
    }
}
 
print(groupId)
for i in 1...groupId {
    result.append(groups[i])
}
result.sorted().map { print($0) }