[코딩테스트] 🦈 아기 상어 - BJ16236

문제링크

난이도

골드 3

유형

구현, BFS

소요시간

1시간 + GPT

회고

알고리즘은 BFS인데, 상태관리와 자잘한 조건 처리가 까다로웠다.

코드

let N = Int(readLine()!)!
var board = [[Int]]()
var sharkR = 0, sharkC = 0

for i in 0..<N {
    let row = readLine()!.split(separator: " ").map { Int($0)! }
    board.append(row)
    if let j = row.firstIndex(of: 9) {
        sharkR = i; sharkC = j
        board[i][j] = 0
    }
}

let dr = [-1, 0, 0, 1]
let dc = [0, -1, 1, 0]

func bfs(_ sr: Int, _ sc: Int, _ size: Int) -> (Int, Int, Int)? {
    var visited = Array(repeating: Array(repeating: false, count: N), count: N)
    var q: [(Int, Int, Int)] = []
    var head = 0
    q.append((sr, sc, 0))
    visited[sr][sc] = true

    var minDist = Int.max
    var target: (Int, Int)? = nil

    while head < q.count {
        let (r, c, d) = q[head]; head += 1
        if d > minDist { break } // 더 먼 곳은 볼 필요 없음

        // 먹이 후보
        if board[r][c] > 0 && board[r][c] < size {
            if d < minDist {
                minDist = d
                target = (r, c)
            } else if d == minDist {
                // 위 → 왼쪽 우선
                if let t = target {
                    if r < t.0 || (r == t.0 && c < t.1) {
                        target = (r, c)
                    }
                }
            }
        }

        // 인접 확장
        for k in 0..<4 {
            let nr = r + dr[k], nc = c + dc[k]
            guard 0 <= nr, nr < N, 0 <= nc, nc < N else { continue }
            if visited[nr][nc] { continue }
            // 통과 가능 조건: 칸의 값 <= 상어 크기
            if board[nr][nc] <= size {
                visited[nr][nc] = true
                q.append((nr, nc, d + 1))
            }
        }
    }

    if let t = target {
        return (t.0, t.1, minDist)
    } else {
        return nil
    }
}

var size = 2
var eaten = 0
var time = 0

while true {
    if let (tr, tc, dist) = bfs(sharkR, sharkC, size) {
        time += dist
        sharkR = tr; sharkC = tc
        board[tr][tc] = 0
        eaten += 1
        if eaten == size {
            size += 1
            eaten = 0
        }
    } else {
        break
    }
}

print(time)