Swift) 백준 16236번 아기 상어 - G3

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

16236번: 아기 상어

문제를 잘읽자!!

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지는 모두 지나갈 수 있다. 

상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 

상어의 시작 크기는 2이다.

 

문제를 잘 안읽어서 시간만 30분 넘게 잡아먹었다. 문제를 반드시 자세히 읽자.

 

상어는 가장 가까운 물고기를 우선순위에 둔다. 이때, 가장 가까운 물고기가 여럿 있을 경우 가장 위에 있는 물고기가 1순위, 그리고 가장 왼쪽에 있는 물고기를 2순위로 먹는다.

 

그래서 일단은 bfs로 상어가 먹을 수 있는 물고기의 최소 길이를 구했다. 

순서는 위, 왼쪽, 오른쪽, 아래 순서로 탐색. 

 

주의할점은 bfs로 처음 물고기를 만난게 가장 우선순위가 높은 물고기를 만난게 아니다.

bfs로 처음 탐색을 하면 위 사진과 같은 순서로 탐색한 후, 방문 유무를 체크한 후 위 순서대로 큐에서 꺼내서 다시 탐색을 할것이다.

하지만 다음 탐색에서 9번째 탐색이 10번째 탐색보다 아랫쪽에 있음에도 먼저 탐색 되었다. 

따라서 bfs로 가장 먼저 만난 물고기가 가장 우선순위가 높은 물고기임을 보장해주지 않으므로 가장 먼저 만난 먹을 수 있는 물고기의 distance를 저장한 후, distance 이하의 먹을 수 있는 물고기를 탐색한 후 정렬을 통해 문제를 해결했다. 

 

추가로 처음 공간이 주어질때 상어의 위치가 9로 표시되는데, 이때 상어의 크기가 9보다 커지게 되면 이것도 물고기로 인식하게 되므로, while문이 돌기 전에 해당 위치를 0으로 바꾸어야 한다.

import Foundation

let n = Int(readLine()!)!
var map: [[Int]] = []
var visitedMap: [[Bool]] = Array(repeating: Array(repeating: false, count: n), count: n)

var currentSharkSize = 2
var eatFishCount = 0
var currentSharkLocation: (Int, Int) = (0,0)

var answer = 0
let di = [-1, 0, 0, 1]
let dj = [0, -1, 1, 0]

for i in 0..<n {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    if input.contains(9) {
        let index = input.firstIndex(of: 9)!
        currentSharkLocation = (i, index)
    }
    map.append(input)
}

func initalVisitMap() {
    visitedMap = Array(repeating: Array(repeating: false, count: n), count: n)
}

func findCanEatFish(i: Int, j: Int) -> [(Int, Int, Int)] {
    var queue: [(Int, Int, Int)] = []
    var minDistance = Int.max
    queue.append((i,j, 0))
    var minFishLocationArr: [(Int, Int, Int)] = []
    
    while !queue.isEmpty {
        let popLocation = queue.removeFirst()
        for num in 0..<4 {
            let ni = di[num]
            let nj = dj[num]
            let moveLocation = (popLocation.0+ni, popLocation.1+nj)
            let distance = popLocation.2+1
            if moveLocation.0 < 0 || moveLocation.0 >= n || moveLocation.1 < 0 || moveLocation.1 >= n {
                continue
            }
            if visitedMap[moveLocation.0][moveLocation.1] || map[moveLocation.0][moveLocation.1] > currentSharkSize {
                continue
            }
            visitedMap[moveLocation.0][moveLocation.1] = true
            if map[moveLocation.0][moveLocation.1] < currentSharkSize && map[moveLocation.0][moveLocation.1] != 0 {
                if distance <= minDistance {
                    minDistance = min(minDistance, distance)
                    minFishLocationArr.append((moveLocation.0, moveLocation.1, distance))
                }
            }
            if distance <= minDistance {
                queue.append((moveLocation.0, moveLocation.1, distance))
            }
            
        }
    }
    return minFishLocationArr
}

func eatFishAction(i: Int, j: Int, distance: Int) {
    answer += distance
    currentSharkLocation.0 = i
    currentSharkLocation.1 = j
    map[i][j] = 0
    eatFishCount += 1
    if currentSharkSize == eatFishCount {
        currentSharkSize += 1
        eatFishCount = 0
    }
}

map[currentSharkLocation.0][currentSharkLocation.1] = 0

while true {
    visitedMap[currentSharkLocation.0][currentSharkLocation.1] = true
    let eatFish = findCanEatFish(i: currentSharkLocation.0, j: currentSharkLocation.1)
    if eatFish.count == 0 {
        break
    } else if eatFish.count == 1 {
        let fishLocation = eatFish[0]
        eatFishAction(i: fishLocation.0, j: fishLocation.1, distance: fishLocation.2)
    } else {
        let sortedEatFish = eatFish.sorted { first, second  in
            if first.0 == second.0 {
                return first.1 < second.1
            }
            return first.0 < second.0
        }
        let fishLocation = sortedEatFish[0]
        eatFishAction(i: fishLocation.0, j: fishLocation.1, distance: fishLocation.2)
    }
    initalVisitMap()
}

print(answer)