[BFS] 백준: 단지번호붙이기(Swift)

난이도: 실버1

사용 언어: Swift

카테고리: BFS

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

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 n = Int(readLine()!)!
var map = [[Int]]()
var countArr = [Int]()

for _ in 0..<n {
  let input = readLine()!
  let l = Array(input).map { Int(String($0))! }
  map.append(l)
}

func bfs(start: (y: Int, x: Int)) -> Int {
  let lrud: [(y: Int, x: Int)] = [
    (0,-1),
    (0,1),
    (-1,0),
    (1,0)
  ]
  var count = 1
  var queue = Queue<(y: Int, x: Int)>()
  queue.inQueue(element: start)
  let (y,x) = start
  map[y][x] = 0
  
  while !queue.isEmpty {
    let p = queue.deQueue()
    
    for i in 0..<4 {
      let next = (p.y + lrud[i].y, p.x + lrud[i].x)
      if (0..<n).contains(next.0) && (0..<n).contains(next.1) {
        if map[next.0][next.1] == 1 {
          map[next.0][next.1] = 0
          count += 1
          queue.inQueue(element: next)
        }
      }
    }
  }
  return count
}


for y in 0..<n {
  for x in 0..<n {
    if map[y][x] == 1 {
      let result = bfs(start: (y,x))
      countArr.append(result)
    }
  }
}

print(countArr.count)
countArr.sorted(by: <)
  .forEach {
  print($0)
}