[BFS] 백준: 섬의 개수(Swift)

난이도: 실버2

사용 언어: Swift

카테고리: BFS

 

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

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
  }
}



var results = [Int]()
while true {
  let wh = readLine()!.split(separator: " ").map { Int($0)! }
  let w = wh[0]
  let h = wh[1]
  
  if w == 0 && h == 0 { break }

  var map = [[Int]]()

  for _ in 0..<h {
    let y = readLine()!.split(separator: " ").map { Int($0)! }
    map.append(y)
  }

  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 direction: [(y: Int, x: Int)] = [
      (0,-1),
      (0,1),
      (-1,0),
      (1,0),
      (-1,-1),
      (-1,1),
      (1,-1),
      (1,1)
    ]
    while !q.isEmpty {
      let currentPoint: (y: Int, x: Int) = q.deQueue()
      
      for i in 0..<direction.count {
        let nextPoint: (y: Int, x: Int) = (currentPoint.y + direction[i].y, currentPoint.x + direction[i].x)
        if (0..<h).contains(nextPoint.y) && (0..<w).contains(nextPoint.x) && map[nextPoint.y][nextPoint.x] == 1 {
          map[nextPoint.y][nextPoint.x] = 0
          q.inQueue(element: nextPoint)
        }
      }
    }
  }

  for y in 0..<h {
    for x in 0..<w {
      if map[y][x] == 1 {
        bfs(start: (y, x))
      }
    }
  }
  results.append(result)
}

results.forEach { result in
  print(result)
}