백준 - 아기 상어(Swift)

백준 - 아기 상어(Swift)

 

 

 문제 설명

 

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

16236번: 아기 상어

 

 나의 풀이

 

다른 분의 블로그를 참고했지만 이제 이런 문제는 풀 줄 알아야한다.

아기상어의 위치에서 최소의 위치를 찾는 것은 BFS이며 2차원 배열을 기존의 배열, 근접한 물고기들의 배열을 선언함으로써 문제를 풀었다.

 

그리고 자신보다 큰 물고기의 경우에는 아예 어떠한 로직도 거치지 않음으로써 무시하고 지나갈 수 있게 만들었다.

마지막으로 방문표시를 하는 이유는 그 거리까지는 이미 최소이기 때문에 또 갱신하지 말아야 하기 때문이다. (방문표시는 0이 아니라면 방문표시가 된 것으로 간주했다)

 

import Foundation

let N = Int(readLine()!)!
let dx = [-1, 0, 1, 0]
let dy = [0, -1, 0, 1]
var arr = [[Int]]()
var shark = (0, 0)
var queue = [(Int, Int)]()
var distance = [[Int]]()
var fish = [(Int, Int, Int)]()
var result = 0
var size = 2
var exp = 0
let xRange = 0..<N
let yRange = 0..<N
for _ in 0..<N {
    arr.append(readLine()!.components(separatedBy:" ").map{Int($0)!})
}

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

func BFS() {
    var index = 0
    distance[shark.0][shark.1] = 1 // 상어가 있는 곳에 방문표시
    queue.append((shark.0, shark.1))
    
    while index < queue.count {
        let cur = queue[index]
        index += 1
        
        for i in 0..<4 {
            var nx = cur.0 + dx[i]
            var ny = cur.1 + dy[i]
            
            // 범위안에 있고, 방문하지 않은 것들에 대해서만 탐색
            if xRange ~= nx, yRange ~= ny, distance[nx][ny] == 0 {
                // 물고기가 존재하고 그 물고기가 현재 상어보다 작다면
                if arr[nx][ny] != 0, arr[nx][ny] < size {
                    distance[nx][ny] = distance[cur.0][cur.1] + 1
                    fish.append((nx, ny, distance[nx][ny]))
                } 
                // 물고기가 존재하지않거나 그 물고기가 현재 상어와 크기가 같다면 
                if arr[nx][ny] == 0 || arr[nx][ny] == size {
                    distance[nx][ny] = distance[cur.0][cur.1] + 1
                    queue.append((nx, ny))
                } 
            }
        }
        
    }
    
}

while true {
    queue = [(Int, Int)]()
    distance = Array(repeating: Array(repeating: 0, count: N), count: N)
    fish = [(Int, Int, Int)]()
    BFS()
    
    if fish.isEmpty {
        print(result)
        break
    }
    
    fish = fish.sorted { $0.2 == $1.2 ? 
                        ( $0.0 == $1.0 ? $0.1 < $1.1 : $0.0 < $1.0) :
                        $0.2 < $1.2 }
    
    shark = (fish[0].0, fish[0].1) // 상어 현재위치 변경
    exp += 1
    if size == exp { size += 1; exp = 0 } // 경험치가 도달했ㄷ자면 size를 키운다.
    arr[fish[0].0][fish[0].1] = 0 // 상어가 도달했으니 해당자리를 0으로 리셋
    result += (fish[0].2 - 1) // 아기상어에서 물고기까지의 거리를 추가. 1을 빼는 이유는 방문표시를 위해 처음에 1을 설정했기 때문
}