문제 링크 (opens new window)

문제 요약

1. 상하좌우로 인접한 집들을 한 단지로 묶는다
2. 전체 지도에서 단지 수를 출력한다
3. 단지 내 집 수를 출력한다.

접근 방식

1. DFS를 활용하여 연결된 컴포넌트 수를 출력한다.
2. DFS과정에서 순회중인 위치 인접리스트 값이 1인 경우 +1 하여 리턴 -> 단지 내 집 갯수 출력을 위함
3. 시간복잡도는 N+간선 수

풀이

import Foundation

let N = Int(readLine()!)!
var adj: [[Int]] = .init(repeating: .init(repeating: 0, count: N), count: N)
var visited: [[Bool]] = .init(repeating: .init(repeating: false, count: N), count: N)
let dy = [-1, 0, 1, 0]; let dx = [0, 1, 0, -1]
var ret = 0
var result: [Int] = []

for i in 0..<N {
    adj[i] = readLine()!.map { Int(String($0))! }
}

func dfs(_ y: Int, _ x: Int) -> Int {
    var ret = 1
    visited[y][x] = true

    for i in 0..<4 {
        let ny = dy[i] + y
        let nx = dx[i] + x

        if ny < 0 || nx < 0 || ny >= N || nx >= N || visited[ny][nx] || adj[ny][nx] == 0 {
            continue
        }

        ret += dfs(ny, nx)
    }

    return ret
}

for i in 0..<N {
    for j in 0..<N {
        if visited[i][j] || adj[i][j] == 0 { continue }
        result.append(dfs(i, j))
        ret += 1
    }
}
print(ret)
result.sorted().forEach { print($0) }