[구현 + BFS] 백준 골드3 16236번: 아기 상어(Swift)

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

16236번: 아기 상어

풀이과정

해당 문제는 상어가 먹이를 찾아 먹는 과정에서 이동 거리(시간)을 계산하는 문제이다.

상어가 이동할 수 있는 조건은 물고기가 없는 빈칸(0)이거나 자신보다 사이즈가 같거나 작아야 한다.

또한 먹이는 자신보다 작은 물고기만 먹을 수 있으며, 가까운 순서로 먹는다.

만약 거리가 같은 물고기가 둘 이상이 있다면,

먼저 가장 위에 있는 물고기 그중에서 가장 왼쪽에 있는 물고기를 우선으로 먹는다.

위 문제는 그래프 탐색이기 때문에 BFS를 이용하여 문제를 풀 수 있다.

먼저, 입력 값을 그래프에 저장하고, 상어의 위치를 파악한다.

let n = Int(readLine()!)!
var map = [[Int]]()
var sharkY = 0
var sharkX = 0

for i in 0..<n {
  let y = readLine()!.split(separator: " ").map { Int($0)! }
  map.append(y)
  
  if let j = y.firstIndex(of: 9) {
    sharkY = i
    sharkX = j
    map[i][j] = 0
  }
}

상어의 위치를 파악하고 해당 위치의 좌표값을 저장 후 해당 위치는 빈칸으로 만든다.

이후 상어의 사이즈와 먹은 먹이 수를 카운팅 할 수 있는 변수를 만들고, bfs 메서드를 구현한다.

var size = 2
var eatCount = 0

func bfs() -> Int? {
  let dy = [1, 0, -1, 0]
  let dx = [0, 1, 0, -1]
  
  var visited = Array(repeating: Array(repeating: false, count: n),count: n)
  visited[sharkY][sharkX] = true
  
  var queue = Queue<(y: Int, x: Int, move: Int)>()
  queue.inQueue(element: (sharkY, sharkX, 0))
  
  var min = Int.max
  var fish = [(y: Int, x: Int)]()
  
  while !queue.isEmpty {
    let (y, x, move) = queue.deQueue()
    
    if move > min { continue }
    
    if (1..<size).contains(map[y][x]) {
      min = move
      fish.append((y, x))
    }
    
    for i in 0..<4 {
      let (nextY, nextX) = (y + dy[i], x + dx[i])
      if (0..<n).contains(nextY)
          && (0..<n).contains(nextX)
          && !visited[nextY][nextX]
          && map[nextY][nextX] <= size {
        visited[nextY][nextX] = true
        queue.inQueue(element: (nextY, nextX, move + 1))
      }
    }
  }
  
  if fish.isEmpty {
    return nil
  }
  
  fish.sort {
    if $0.y == $1.y {
      return $0.x < $1.x
    }
    return $0.y < $1.y
  }
  
  let sharkYX = fish.first!
  eatCount += 1
  
  if eatCount == size {
    size += 1
    eatCount = 0
  }
  
  map[sharkYX.y][sharkYX.x] = 0
  sharkY = sharkYX.y
  sharkX = sharkYX.x
  
  return min
}

visited 배열을 통해 경로가 중복되는 것을 방지하고,

최단거리의 먹을 수 있는 물고기의 좌표를 저장할 변수 fish를 만든다.

단, 둘 이상일 수 있기 때문에 배열로 만들어 준다.

거리는 min과 move를 통해 최단거리인지 판별한다.

가장 가까운 거리이면서, 상어보다 사이즈가 작다면, fish에 해당 좌표를 담는다.

좌표를 이동하며 위 과정을 반복한다.

먹이 탐색이 끝났으면, 먹을 수 있는 fish가 있는지 체크한다.

만약, 없다면 nil을 반환하고 메서드를 종료한다.

먹이가 있다면, 먹이 우선순위에 맞게 배열을 정렬하고,

먹이 좌표로 상어를 이동시킨 뒤 eatCount를 올려준다.

이후 조건에 맞게 먹은 먹이 수와 사이즈가 같다면 사이즈를 키워주고, eatCount는 다시 0으로 초기화 시킨다.

또한, 먹이를 먹은 위치는 0(빈칸)으로 초기화해준다.

마지막으로 최단거리(min)을 리턴하고 메서드를 마무리한다.

var result = 0

while true {
  if let time = bfs() {
    result += time
  } else {
    print(result)
    break
  }
}

이젠, 위 코드와 같이 bfs가 nil을 반환할 때까지 반복해 주며, 반환값은 result에 담아준다.

전체코드

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 sharkY = 0
var sharkX = 0

for i in 0..<n {
  let y = readLine()!.split(separator: " ").map { Int($0)! }
  map.append(y)
  
  if let j = y.firstIndex(of: 9) {
    sharkY = i
    sharkX = j
    map[i][j] = 0
  }
}

var size = 2
var eatCount = 0

func bfs() -> Int? {
  let dy = [1, 0, -1, 0]
  let dx = [0, 1, 0, -1]
  
  var visited = Array(repeating: Array(repeating: false, count: n),count: n)
  visited[sharkY][sharkX] = true
  
  var queue = Queue<(y: Int, x: Int, move: Int)>()
  queue.inQueue(element: (sharkY, sharkX, 0))
  
  var min = Int.max
  var fish = [(y: Int, x: Int)]()
  
  while !queue.isEmpty {
    let (y, x, move) = queue.deQueue()
    
    if move > min { continue }
    
    if (1..<size).contains(map[y][x]) {
      min = move
      fish.append((y, x))
    }
    
    for i in 0..<4 {
      let (nextY, nextX) = (y + dy[i], x + dx[i])
      if (0..<n).contains(nextY)
          && (0..<n).contains(nextX)
          && !visited[nextY][nextX]
          && map[nextY][nextX] <= size {
        visited[nextY][nextX] = true
        queue.inQueue(element: (nextY, nextX, move + 1))
      }
    }
  }
  
  if fish.isEmpty {
    return nil
  }
  
  fish.sort {
    if $0.y == $1.y {
      return $0.x < $1.x
    }
    return $0.y < $1.y
  }
  
  let sharkYX = fish.first!
  eatCount += 1
  
  if eatCount == size {
    size += 1
    eatCount = 0
  }
  
  map[sharkYX.y][sharkYX.x] = 0
  sharkY = sharkYX.y
  sharkX = sharkYX.x
  
  return min
}

var result = 0

while true {
  if let time = bfs() {
    result += time
  } else {
    print(result)
    break
  }
}