[BFS] 백준: 영역 구하기(Swift)

난이도: 실버 1

사용 언어: Swift

카테고리: BFS

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

2583번: 영역 구하기

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 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: false, count: n), count: m)

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

var q = Queue<(y: Int, x: Int)>()
let direction: [(y: Int, x: Int)] = [
  (0,-1),
  (0,1),
  (-1,0),
  (1,0)
]
var count = 0
func bfs(start: (y: Int, x: Int)) -> Int {
  map[start.y][start.x] = true
  count += 1
  q.inQueue(element: start)
  var r = 1
  while !q.isEmpty {
    let cP = q.deQueue()
    for i in 0..<direction.count {
      let nP: (y: Int, x: Int) = (cP.y + direction[i].y, cP.x + direction[i].x)
      if (0..<m).contains(nP.y)
          && (0..<n).contains(nP.x)
          && !map[nP.y][nP.x] {
        map[nP.y][nP.x] = true
        r += 1
        q.inQueue(element: nP)
      }
    }
  }
  return r
}

var arr = [Int]()

for y in 0..<m {
  for x in 0..<n {
    if !map[y][x] {
      arr.append(bfs(start: (y, x)))
    }
  }
}

print(count)
arr.sorted(by: <).forEach {
  print($0, terminator: " ")
}