백준 2667번 단지번호붙이기 - 스위프트(Swift) 풀이 + 그림 설명

1. 각 집을 그래프의 정점으로 생각한다.
2. 어떤 집을 시작점으로 DFS/BFS를 하면 해당 집이 속하는 단지 내의 모든 집을 방문할 수 있다.
3. 따라서 DFS/BFS의 호출 횟수가 곧 단지의 개수이고,
4. DFS/BFS를 돌면서 방문한 정점의 수가 한 단지 내에 속한 집의 수이다.

---

1. 각 집을 그래프의 정점으로 생각한다.

 0인 곳은 갈 수 없으므로 무시하고, 1인 곳을 정점이라고 생각한다.

 

 

2. 어떤 집을 시작점으로 DFS/BFS를 하면 해당 집이 속하는 단지 내의 모든 집을 방문할 수 있다.

 (1, 1)을 시작점으로 그래프를 탐색해주면, 해당 단지 내의 모든 집을 방문할 수 있다. 탐색 방법은 DFS/BFS를 쓰면 된다. 이때 연결되지 않은 (1,4)와 (2,4)가 속한 단지는 방문을 하지 못한다.

 

 

3. 따라서 DFS/BFS의 호출횟수가 곧 단지의 개수이고,

 모든 집을 차례로 확인하면서 아직 방문하지 않은 곳이면, 그 집을 시작점으로 DFS/BFS를 해준다. 그럼 그 집이 속한 단지 내 모든 집을 방문할 수 있다. 따라서 DFS/BFS는 총단지의 수만큼 호출될 것이다. 위의 그림에서 (1,4)는 아직 방문하지 않았으므로 (1,4)를 시작점으로 DFS/BFS를 해준다. 두 번째 호출이므로 2번째 단지가 되는 것이다.

 

 

4. DFS/BFS를 돌면서 방문한 정점의 수가 한 단지 내에 속한 집의 수이다.

 단지의 수 뿐만아니라 각 단지 내에 속한 집의 수들도 출력해야 하므로, DFS/BFS를 돌 때 방문한 정점의 수도 기록해두어야 한다.

 

---

import Foundation

var visit = Array(repeating: Array(repeating: false, count: 27), count: 27)
var map = Array(repeating: Array(repeating: 0, count: 27), count: 27)
var N = 0
var depth = 0

typealias Adjacent = (dr: Int, dc: Int)

func DFS(row: Int, col: Int) {
    depth += 1                  // 단지에 속하는 집의 수 기록
    visit[row][col] = true
    
    let adjacents: [Adjacent] = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for adj in adjacents {
        let adjRow = row + adj.dr
        let adjCol = col + adj.dc
        
        if !visit[adjRow][adjCol] && map[adjRow][adjCol] == 1 {
            DFS(row: adjRow, col: adjCol)
        }
    }
}

func countCC() -> [Int] {
    var ret = [Int]()
    
    for row in 1...N {
        for col in 1...N {
            if !visit[row][col] && map[row][col] == 1 {
                DFS(row: row, col: col)         // DFS 호출 횟수 = 단지 개수
                
                ret.append(depth)
                depth = 0
            }
        }
    }
    
    return ret.sorted()
}

func solution() {
    N = Int(readLine()!)!
    
    for i in 1...N {
        let row = readLine()!
        
        row.enumerated().forEach {
            map[i][$0 + 1] = Int(String($1))!
        }
    }
    
    let countingResult = countCC()
    
    var result = ""
    result.write("\(countingResult.count)\n")
    countingResult.forEach{ result.write("\($0)\n") }
    print(result)
}

solution()