16236 swift - 아기 상어
2023. 3. 3. 19:06ㆍ카테고리 없음
사용 알고리즘 BFS
[Swift] Breadth-First Search / BFS
BFS (Breadth-First Search) 인접한 노드를 먼저 탐색하는 방식. O(Vertex+Edge) A→B→C→D→E→F→G→H 해당하는 그래프는 아래와 같이 인접 리스트로 나타낼 수 있다. let graph: [String: [String]] = [ "A" : ["B", "C"],
chanhhh.tistory.com
사용 자료구조 Queue
[Swift] (자료구조) 큐 / Queue
import Foundation class Queue { var enQueue: [T] = [] var deQueue: [T] = [] var count: Int { return enQueue.count + deQueue.count } var isEmpty: Bool { return enQueue.isEmpty && deQueue.isEmpty } init() { } func push(_ element: T) { enQueue.append(element)
chanhhh.tistory.com
사용 대표 문법 Tuple, typealias
//
// 16236_아기 상어.swift
// swift_practise
//
// Created by Chan on 2023/03/03.
//
// https://www.acmicpc.net/problem/16236
//
// MARK: - BFS
typealias Coord = (x: Int, y: Int)
typealias EatCount = Int
typealias Size = Int
let n = Int(readLine()!)!
var map = [[Int]]()
var sharkInfo = (Coord(0, 0), Size(2), EatCount(0))
var allowedRanges = (0..<n)
var time = 0
for i in 0..<n {
let k = readLine()!.split(separator: " ").map{Int(String($0))!}
map.append(k)
if k.contains(9) {
sharkInfo.0.x = i
sharkInfo.0.y = k.firstIndex(of: 9)!
map[sharkInfo.0.x][sharkInfo.0.y] = 0
}
}
func bfs() -> Bool {
let d = [(0, -1), (-1, 0), (1, 0), (0, 1)]
var q = [(sharkInfo.0.x, sharkInfo.0.y, 0)]
var i = 0
var visitedMap = Array(repeating: Array(repeating: false, count: n), count: n)
var dist = Int.max
var fishList = [(Int, Int)]()
while q.count > i {
let (x, y, cnt) = q[i]
i += 1
if cnt > dist {continue}
if aroundCheck(x, y, sharkInfo.1) {
dist = cnt
fishList.append((x, y))
}
for i in 0..<4 {
let (nx, ny) = (x+d[i].0, y+d[i].1)
if allowedRanges.contains(nx) && allowedRanges.contains(ny) && !visitedMap[nx][ny] && map[nx][ny] <= sharkInfo.1 {
visitedMap[nx][ny] = true
q.append((nx,ny,cnt+1))
}
}
}
if fishList.isEmpty {
return true
}
fishList.sort{
if $0.0 == $1.0 {
return $0.1 < $1.1
}
return $0.0 < $1.0
}
let target = fishList.first!
sharkInfo.2 += 1
if sharkInfo.1 == sharkInfo.2 {
sharkInfo.1 += 1
sharkInfo.2 = 0
}
map[target.0][target.1] = 0
sharkInfo = ((target.0, target.1), sharkInfo.1, sharkInfo.2)
time += dist
return false
}
while true {
if bfs() {
print(time)
break
}
}
func aroundCheck(_ i: Int, _ j: Int, _ s: Int) -> Bool {
if map[i][j] < s && map[i][j] != 0 { return true }
return false
}