[BFS] 백준: 유기농 배추(Swift)

난이도: 실버2

사용 언어: Swift

카테고리: BFS

https://www.acmicpc.net/problem/1012

Code

struct Queue<T> {
  var memory = [T]()
  var index = 0
  
  var isEmpty: Bool {
    memory.count < index + 1
  }
  
  mutating func inQueue(element: T) {
    memory.append(element)
  }
  
  mutating func deQueue() -> T {
    let v = memory[index]
    index += 1
    return v
  }
}

let t = Int(readLine()!)!
var results = [Int]()
for _ in 0..<t {
  let result = start()
  results.append(result)
}

for p in results {
  print(p)
}

func start() -> Int {
  let mnk = readLine()!.split(separator: " ").map { Int($0)! }
  let m = mnk[0]
  let n = mnk[1]
  let k = mnk[2]

  var map = Array(repeating: Array(repeating: 0, count: m), count: n)

  for _ in 0..<k {
    let xy = readLine()!.split(separator: " ").map { Int($0)! }
    map[xy[1]][xy[0]] = 1
  }

  var result = 0

  func bfs(start: (y: Int, x: Int)) {
    result += 1
    map[start.y][start.x] = 0
    var q = Queue<(y: Int, x: Int)>()
    q.inQueue(element: start)
    
    let lrud: [(y: Int, x: Int)] = [
        (0,-1),
        (0,1),
        (-1,0),
        (1,0)
      ]
    
    while !q.isEmpty {
      let (newY, newX) = q.deQueue()
      
      for (my, mx) in lrud {
        let next: (y: Int, x: Int) = (my + newY, mx + newX)
        if (0..<n).contains(next.y) && (0..<m).contains(next.x) && map[next.y][next.x] == 1 {
          map[next.y][next.x] = 0
          q.inQueue(element: next)
        }
      }
    }
  }

  for i in 0..<n {
    for j in 0..<m {
      if map[i][j] == 1 {
        bfs(start: (i, j))
      }
    }
  }
  return result
}