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

2023. 6. 22. 21:35·코테

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

 

16236번: 아기 상어

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가

www.acmicpc.net

풀이과정

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

상어가 이동할 수 있는 조건은 물고기가 없는 빈칸(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
  }
}

 

저작자표시 (새창열림)

'코테' 카테고리의 다른 글

[완전 탐색] 백준 실버4 1018번: 체스판 다시 칠하기(Swift)  (0) 2023.07.13
[구현] 백준 실버3 2503번: 숫자 야구(Swift)  (0) 2023.07.08
[구현 + 재귀] 백준 골드5 14891번: 톱니바퀴(Swift)  (0) 2023.06.22
[백트래킹 + 구현] 백준 실버1 14888번: 연산자 끼워넣기(Swift)  (0) 2023.06.09
[백트래킹 + 구현] 백준 실버2 14889번 스타트와 링크(Swift)  (0) 2023.06.09
'코테' 카테고리의 다른 글
  • [완전 탐색] 백준 실버4 1018번: 체스판 다시 칠하기(Swift)
  • [구현] 백준 실버3 2503번: 숫자 야구(Swift)
  • [구현 + 재귀] 백준 골드5 14891번: 톱니바퀴(Swift)
  • [백트래킹 + 구현] 백준 실버1 14888번: 연산자 끼워넣기(Swift)
Esiwon
Esiwon
iOS 개발 블로그
  • Esiwon
    시원한 코드 기록
    Esiwon
  • 전체
    오늘
    어제
    • 분류 전체보기 (70)
      • iOS&Swift (24)
      • git & github (1)
      • 코테 (41)
      • 네부캠 회고 (4)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

    • 깃허브
  • 공지사항

  • 인기 글

  • 태그

    재귀
    탐색
    회고
    네부캠
    노드
    photoUI
    알고리즘
    브루트포스 알고리즘
    백준
    Property wrapper
    Swift
    구현
    Race Condition
    비동기
    photos
    챌린지
    BFS
    PhotoKit
    그리디
    dfs
    코딩테스트
    실버
    ios
    코테
    완전탐색
    동시성
    이분탐색
    Combine
    GCD
    다이나믹 프로그래밍
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
Esiwon
[구현 + BFS] 백준 골드3 16236번: 아기 상어(Swift)
상단으로

티스토리툴바