import Foundation

let T = Int(readLine()!)!

for _ in 1...T {
    let MNK = readLine()!.components(separatedBy: " ").map { Int($0)! }
    let M = MNK[0]    // 배추밭 가로길이
    let N = MNK[1]    // 배추밭 새로길이
    let K = MNK[2]    // 배추가 심어져 있는 위치의 개수
    
    // M * N 2차원 배열 생성
    var graph = [[Int]](repeating: [Int](repeating: 0, count: M), count: N)
        
    for _ in 1...K {
        let XY = readLine()!.components(separatedBy: " ").map { Int($0)! }
        let X = XY[0]    // 배추 위치
        let Y = XY[1]
        graph[Y][X] = 1
    }
    
    func dfs(_ x: Int, _ y: Int) {
        // (0, 0) ~ (M, N)을 벗어나면 리턴
        if x < 0 || x >= M || y < 0 || y >= N {
            return
        }
        // 배추가 있을 경우 동서남북 방향으로 dfs 호출하여 배추를 없애버림
        // (이어져 있는건 한개로 쳐야하니까)
        if graph[y][x] == 1 {
            graph[y][x] = 0
            dfs(x+1, y)
            dfs(x-1, y)
            dfs(x, y+1)
            dfs(x, y-1)
        }
    }
    
    var cnt = 0
    
    // 2차원 배열의 모든 좌표를 돌며 배추가 있을 경우 dfs 호출
    for i in 0..<N {
        for j in 0..<M {
            if graph[i][j] == 1 {
                dfs(j, i)
                cnt += 1
            }
        }
    }
    
    print(cnt)
}
반응형
JerryiOS