[BFS + 구현] 백준 2573번: 빙산

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

2573번: 빙산

난이도

골드 4

사용언어

swift

카테고리

BFS + 구현

풀이과정

첫 제출 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 nm = readLine()!.split(separator: " ").map { Int($0)! }
let n = nm[0]
let m = nm[1]

var map = [[Int]]()
var s = Array(repeating: Array(repeating: 0, count: m), count: n)
var visited = Array(repeating: Array(repeating: false, count: m), count: n)
var count = 0

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

var q = Queue<(y: Int, x: Int)>()
let direction: [(y: Int, x: Int)] = [
  (0,-1),
  (0,1),
  (-1,0),
  (1,0)
]

func bfs(start: (y: Int, x: Int)) {
  q.inQueue(element: start)
  visited[start.y][start.x] = true
  count += 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 map[np.y][np.x] == 0 {
        s[cp.y][cp.x] += 1
      }
      if (0..<n).contains(np.y) &&
          (0..<m).contains(np.x) &&
          !visited[np.y][np.x] &&
          map[np.y][np.x] != 0 {
        visited[np.y][np.x] = true
        q.inQueue(element: np)
      }
    }
  }
}

func next() {
  for y in 0..<n {
    for x in 0..<m {
      map[y][x] -= s[y][x]
      if map[y][x] < 0 {
        map[y][x] = 0
      }
    }
  }
  s = Array(repeating: Array(repeating: 0, count: m), count: n)
  visited = Array(repeating: Array(repeating: false, count: m), count: n)
  count = 0
}
var result = 0
while true {
  for y in 0..<n {
    for x in 0..<m {
      if map[y][x] != 0 &&
          !visited[y][x] {
        bfs(start: (y, x))
      }
    }
  }
  if count == 1 {
    next()
    result += 1
  } else {
    print(count == 0 ? 0 : result)
    break
  }
}

첫 제출에서 통과가 되었긴 했지만, 시간이 884ms가 나왔다. 어떻게 하면 개선할 수 있을가 생각하며, 블로그를 찾아보던 중

https://velog.io/@aurora_97/%EB%B0%B1%EC%A4%80-2573%EB%B2%88-%EB%B9%99%EC%82%B0-Swift

백준 2573번: 빙산 - Swift

위 블로그 글을 통해서 코드의 문제점을 알 수 있었다. 문제는 모든 좌표를 탐색했기 때문이다. 

위와 같이 빙산이 존재하는 위치를 배열로 따로 관리하여,

사진과 같이 탐색해 주도록 수정하였더니 188ms로 개선할 수 있었다.

최종 코드

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 nm = readLine()!.split(separator: " ").map { Int($0)! }
let n = nm[0]
let m = nm[1]

var map = [[Int]]()
var icePs = [(y: Int, x: Int)]()

for y in 0..<n {
  let v = readLine()!.split(separator: " ").map { Int($0)! }
  map.append(v)
  for x in 0..<m {
    if v[x] != 0 {
      icePs.append((y,x))
    }
  }
}

var q = Queue<(y: Int, x: Int)>()
let direction: [(y: Int, x: Int)] = [
  (0,-1),
  (0,1),
  (-1,0),
  (1,0)
]

func bfs(start: (y: Int, x: Int), visited: inout [[Bool]], removeArr: inout [[Int]]) {
  q.inQueue(element: start)
  visited[start.y][start.x] = true
  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..<n).contains(np.y) &&
          (0..<m).contains(np.x) {
        
        if map[np.y][np.x] == 0 {
          removeArr[cp.y][cp.x] += 1
        } else if !visited[np.y][np.x] &&
                    map[np.y][np.x] != 0 {
          visited[np.y][np.x] = true
          q.inQueue(element: np)
        }
        
      }
    }
  }
}

func nextYear(removeArr: inout [[Int]]) {
  var temp = [(y: Int, x: Int)]()
  for (y, x) in icePs {
    if map[y][x] - removeArr[y][x] > 0 {
      map[y][x] -= removeArr[y][x]
      temp.append((y, x))
    } else {
      map[y][x] = 0
    }
  }
  icePs = temp
  year += 1
}

var year = 0
while true {
  var removeIceCounts = Array(repeating: Array(repeating: 0, count: m), count: n)
  var visited = Array(repeating: Array(repeating: false, count: m), count: n)
  var count = 0
  
  for (y, x) in icePs {
    if !visited[y][x] {
      bfs(start: (y, x), visited: &visited, removeArr: &removeIceCounts)
      count += 1
    }
  }
  if count == 1 {
    nextYear(removeArr: &removeIceCounts)
  } else {
    print(count == 0 ? 0 : year)
    break
  }
}