[BFS] 백준: 적록색약(Swift)

난이도: 골드 5

사용 언어: Swift

카테고리: BFS

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

10026번: 적록색약

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 = [[Character]]()
var rbMap = [[Character]]()
for _ in 0..<n {
  let y = Array(readLine()!)
  map.append(y)
  rbMap.append(y.map { $0 == "G" ? "R" : $0 })
}

func bfs(start: (y: Int, x: Int), target: Character) -> Int {
  map[start.y][start.x] = "X"
  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)
  ]
  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..<n).contains(nextPoint.y)
          && (0..<n).contains(nextPoint.x)
          && map[nextPoint.y][nextPoint.x] == target {
        map[nextPoint.y][nextPoint.x] = "X"
        q.inQueue(element: nextPoint)
      }
    }
  }
  return 1
}

var r1 = 0
var r2 = 0
for y in 0..<n {
  for x in 0..<n {
    if map[y][x] != "X" {
      r1 += bfs(start: (y, x), target: map[y][x])
    }
  }
}

map = rbMap
for y in 0..<n {
  for x in 0..<n {
    if map[y][x] != "X" {
      r2 += bfs(start: (y, x), target: map[y][x])
    }
  }
}
print("\(r1) \(r2)")