1012 유기농 배추

Today 8/15

BFS

queue를 사용하는 FIFO형식의 탐색방법이다.

유기농 배추 (My Code)

//1012 유기농 배추
for _ in 0..<Int(readLine()!)! {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let (M, N, k) = (input[0], input[1], input[2])
    var map = Array(repeating: Array(repeating: 0, count: N), count: M)
    for _ in 0..<k {
        let input = readLine()!.split(separator: " ").map{Int(String($0))!}
        map[input[0]][input[1]] = 1
    }
    
    var queue = [(Int, Int)]()
    var count = 0
    
    for row in 0..<M {
        for col in 0..<N {
            if map[row][col] == 1 {
                queue.append((row, col))
                map[row][col] = 0
                while !queue.isEmpty {
                    let node = queue.removeFirst()
                    for i in [(-1, 0),(1, 0),(0, -1),(0, 1)] {
                        let (m, n) = (node.0+i.0, node.1+i.1)
                        if (0..<M).contains(m) && (0..<N).contains(n) && map[m][n] == 1 {
                            queue.append((m, n))
                            map[m][n] = 0
                        }
                    }
                }
                count += 1
            }
        }
    }
    print(count)
}

저번에 DFS로 풀었었는데 BFS로 새로 풀었다.