[Swift] 백준_아기 상어(16236)

문제

 

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

16236번: 아기 상어

 

 

풀이

 

어려웠다...

다른 BFS문제들과 대부분 비슷했지만, 먹이를 먹는 기준때문에 오래걸렸다.

 

처음에는 단순히 dx, dy의 순서만 바꿔서 해결하려고했는데, 이렇게 해서는 풀 수 없다는 것을 알게되었고 정렬을 해야 해결이 된다는 것을 알게되었다.

 

기본적인 BFS를 사용하는 것은 동일하다. 근데 이제 더 이상 갈 곳이 없다면 while문은 종료될 것이다. 이때, 탐색하는 동안 먹을 수 있는 물고기를 fish라는 배열에 담아두었으므로 만약 fish도 비어있다면 그대로 종료해주면된다.

 

하지만 fish가 비어있지않다면 문제의 조건에 따라 순서대로 먹을 수 있도록 정렬을 한 뒤에 맨 앞에 있는 물고기로 정해야한다. 이때, 원소에는 좌표와 거리값이 들어있으므로 result의 값을 eat[2]로 바꿔준다. 

정렬은 문제의 조건 그대로 구현하면된다. 우선, 거리가 가장 가까운게 우선이고, 거리가 같다면 더 위에 있는 것이 우선이고 같은 row에 있다면 더 왼쪽에 있는 것이 우선이 되게 정렬한 뒤에 맨 앞의 물고기를 먹는 것으로 정하면된다.

 

먹은 뒤에는 count가 size와 같아진지 확인해서 같다면 사이즈를 업시켜주면된다. 그리고 먹은 공간은 0으로 바꿔준뒤에 eat을 다시 큐에 넣어 반복해주면된다. 전체 bfs과정을 반복하기때문에 겉에 while문을 하나 더 두었다.

import Foundation

let n = Int(readLine()!)!
var space: [[Int]] = []
for _ in 0..<n {
    space.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}
var size = 2
var count = 0
var queue: [[Int]] = []
var result = 0
var visited = Array(repeating: Array(repeating: false, count: n), count: n)
let dx = [1,0,-1,0]
let dy = [0,1,0,-1]
outer: for i in 0..<n {
    for j in 0..<n {
        if space[i][j] == 9 {
            queue.append([i,j,0])
            visited[i][j] = true
            space[i][j] = 0
            break outer
        }
    }
}
while true {
    var fish: [[Int]] = []
    visited = Array(repeating: Array(repeating: false, count: n), count: n)
    var idx = 0
    while idx < queue.count {
        let current = queue[idx]
        idx += 1
        visited[current[0]][current[1]] = true
        for i in 0..<dx.count {
            let newX = current[0] + dx[i]
            let newY = current[1] + dy[i]
            if newX < 0 || newY < 0 || newX >= n || newY >= n {
                continue
            }
            if space[newX][newY] > size {
                continue
            }
            if !visited[newX][newY] {
                if space[newX][newY] == 0 || space[newX][newY] == size {
                    queue.append([newX,newY,current[2] + 1])
                } else {
                    fish.append([newX,newY,current[2] + 1])
                }
                visited[newX][newY] = true
            }
        }
    }
    if fish.isEmpty {
        print(result)
        break
    }
    fish = fish.sorted {
        if $0[2] == $1[2] {
            if $0[0] == $1[0] {
                return $0[1] < $1[1]
            }
            return $0[0] < $1[0]
        }
        return $0[2] < $1[2]
    }
    let eat = fish.first!
    count += 1
    if count == size {
        size += 1
        count = 0
    }
    space[eat[0]][eat[1]] = 0
    result = eat[2]
    queue.removeAll()
    queue.append(eat)
}

 

 

____________________________________________________________________________________________________

 

정렬해야 한다는 생각을 왜 바로 못했는지...