[BFS] 백준: 안전 영역(Swift)

난이도: 실버 1

사용 언어: Swift

카테고리: BFS

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

 

2468번: 안전 영역

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 mapS = [[Int]]()
var max: Int = 0
var visitedS: [[Bool]] = Array(repeating: Array(repeating: false, count: n), count: n)
for _ in 0..<n {
  let y = readLine()!.split(separator: " ").map { Int($0)! }
  max = max > y.max()! ? max : y.max()!
  mapS.append(y)
}

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

var map = [[Int]]()
var visited = [[Bool]]()
var result = 0
var count = 0

for target in 0...max {
  count = 0
  map = mapS
  visited = visitedS
  for y in 0..<n {
    for x in 0..<n {
      if map[y][x] > target && visited[y][x] == false {
        bfs(start: (y, x), target: target)
      }
    }
  }
  result = result > count ? result : count
}

print(result)