[백준 16236] 아기 상어

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

✍️ 첫번째 접근

조건이 까다로운 BFS문제이다. 문제에서 주어진대로 조건을 생각해서 구현하면 되는데 필자는

먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

해당 조건에 대해 BFS를 돌 때, 아래와 같이 순서를 상 -> 좌 -> 하 -> 우로 결정하여 BFS를 돌았다.

let dx = [-1,0,1,0]
let dy = [0,-1,0,1]

하지만 이 경우 예제 입력 4에서 잘못된 출력이 나온다. 그 이유는 아래 그림에서 (0,2)에서 (0,4)로 가야 올바른 출력이 나오는데 (1,1)로 가기 때문이다.

✍️ 두번째 접근

약간의 힌트를 받아 1번의 BFS로 상 -> 좌 -> 하 -> 우의 순서로만 도는 것이 아닌, BFS를 돌면서 먹을 수 있는 물고기를 모두 저장하고 저장한 물고기를 조건에 맞게 sort하였다. 현재 상어 위치를 정렬된 맨 앞 물고기와 바꾸고 다시 BFS를 돌면서 문제를 해결하였다.

import Foundation

func findShark() {
    for i in 0..<N {
        for j in 0..<N {
            if arr[i][j] == 9 {
                arr[i][j] = 0
                now = (i,j)
            }
        }
    }
}

let dx = [-1,0,1,0]
let dy = [0,-1,0,1]
let N = Int(readLine()!)!
var arr: [[Int]] = []
var shark = 2   // 가장 처음 상어의 크기
var cnt = 0
var result = 0
for _ in 0..<N {
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}
var queue: [(x: Int, y: Int)] = []
var size = Array(repeating: Array(repeating: 0, count: N), count: N)
var fish = [(Int, Int, Int)]() // 먹힌 물고기의 (x 좌표, y 좌표, 아기 상어와의 거리)들을 저장할 배열
var now = (0,0)
findShark()
func bfs() {
    queue.append((now.0,now.1))
    size[now.0][now.1] = 1
    while !queue.isEmpty {
        let cur = queue.first!
        queue.removeFirst()
        if arr.flatMap({$0}).filter({$0 != 0 && $0 < shark}).count < 1 {   // 잡아먹을 수 있는 물고기가 없으므로
            break
        }
        for dir in 0..<4 {
            let nx = cur.x + dx[dir]
            let ny = cur.y + dy[dir]
            if nx < 0 || nx >= N || ny < 0 || ny >= N {
                continue
            }
            if size[nx][ny] != 0 {
                continue
            }
            if arr[nx][ny] > shark {    // 자신보다 큰 크기는 지나갈 수 없으므로
                continue
            }
            if arr[nx][ny] != 0 && arr[nx][ny] < shark {    // 자신보다 작으면 먹을 수 있으므로
                size[nx][ny] = size[cur.x][cur.y] + 1
                fish.append((nx, ny, size[nx][ny]))
                continue
            }
            queue.append((nx,ny))
            size[nx][ny] = size[cur.x][cur.y] + 1
        }
    }
}


while true {
    fish = [(Int, Int, Int)]()
    size = Array(repeating: Array(repeating: 0, count: N), count: N)
    queue = []
    bfs()
    if fish.isEmpty { print(result); break }
    cnt += 1
    fish = fish.sorted {
        if $0.2 <= $1.2 {
            if $0.0 == $1.0 { return $0.1 < $1.1 }
            else { return $0.0 < $1.0 }
        }
        else { return false }
    }
    arr[fish[0].0][fish[0].1] = 0
    result += size[fish[0].0][fish[0].1] - 1
    if shark == cnt {
        shark += 1
        cnt = 0
    }
    now = (fish[0].0, fish[0].1) // 먹은 물고기와 현재 상어 위치 교체
}