[Swift Algorithm] 아기 상어 BOJ #16236

문제

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

16236번: 아기 상어

 

내 문제 풀이

let n = Int(readLine()!)!
var space = [[Int]]() // 주어진 공간에 대한 정보
var fish = [(Int, Int, Int)]() // 먹힌 물고기의 (x 좌표, y 좌표, 아기 상어와의 거리)들을 저장할 배열
var shark = (0, 0) // 상어 위치
var distance = [[Int]]() // 주어진 공간의 칸마다 아기 상어가 해당 위치로 오는데 걸린 거리를 저장
var count = 0 // 아기 상어의 크기 증가를 계산하기 위한 카운트 변수
var size = 2 // 아기 상어 크기
let dx = [0, 0, -1, 1]
let dy = [-1, 1, 0, 0]
var queue = [(Int, Int)]()
var result = 0

for _ in 0..<n { space.append(readLine()!.split(separator: " ").map({Int(String($0))!})) }

func bfs() {
    var index = 0 // index 변수를 이용해서 removeFirst 피해줌
    queue.append(shark) // 큐에 현재 상어 위치 추가
    distance[shark.0][shark.1] = 1 // 해당 위치를 중복해서 탐색하지 않도록, 시작 위치이지만 거리를 1로 설정해주어 차별화해주었음
    
    // 더 이상 탐색해야 할 좌표가 없을 때까지 반복
    while index < queue.count {
        let (x, y) = queue[index]
        index += 1 // queue에 저장되어있는 한 좌표의 탐색을 시작하였으므로, index 한 칸 옮겨주기
        
        // 상하좌우 탐색을 위해 4번 반복
        for i in 0..<4 {
            // 탐색할 좌표 설정
            let nx = x + dx[i]
            let ny = y + dy[i]

            if nx < 0 || ny < 0 || nx >= n || ny >= n || distance[nx][ny] != 0 { continue } // 예외
            
            // 탐색할 자리에 물고기가 있고, 아기 상어보다 사이즈가 작을 때 (물고기 먹기에 성공한 경우)
            if space[nx][ny] != 0 && space[nx][ny] < size {
                distance[nx][ny] = distance[x][y] + 1 // [x][y] 자리에서 한 칸 더 왔음을 표시
                fish.append((nx, ny, distance[nx][ny])) // 먹힌 물고기의 좌표와 거기까지 걸린 거리에 대한 정보를 추가
                continue
            }
            
            // 탐색할 자리에 물고기가 없거나, 아기상어와 사이즈가 같을 때 (아직 먹을 물고기를 찾지 못한 경우)
            if space[nx][ny] == 0 || space[nx][ny] == size {
                distance[nx][ny] = distance[x][y] + 1 // [x][y] 자리에서 한 칸 더 왔음을 표시
                queue.append((nx, ny)) // 탐색해야 할 좌표를 추가
            }
        }
    }
}

for i in 0..<n {
    for j in 0..<n {
        if space[i][j] == 9 { shark = (i, j); space[i][j] = 0 } // 아기 상어의 초기 위치 찾고, 해당 자리는 0으로 채워주기
    }
}

while true {
    // bfs 함수 돌리기 전 초기화
    fish = [(Int, Int, Int)]()
    distance = Array(repeating: Array(repeating: 0, count: n), count: n)
    queue = [(Int, Int)]()
    
    bfs()
    
    if fish.isEmpty { print(result); break } // 이번 bfs 함수 실행에서는 먹힌 물고기가 없다는 뜻으로, result 값을 그대로 출력, 실행 종료 !
    
    count += 1
    
    // 아기 상어와의 거리가 짧았던 것부터 오름차순, x좌표가 작은 것부터 오름차순, y좌표가 작은 것부터 오름차순으로 정렬
    // (아기 상어는 가장 가까운 물고기부터 먹고, 거리가 가까운 물고기가 많다면 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면 가장 왼쪽에 있는 물고기를 먹는다는 조건에 의함)
    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 }
    }
    
    space[fish[0].0][fish[0].1] = 0 // 위에서 조건에 맞게 먹힌 물고기들을 정렬하였을 때, 가장 먼저 먹히는게 맞는 물고기의 자리를 0으로 바꿔줌
    result += distance[fish[0].0][fish[0].1] - 1 // 해당 물고기와 아기 상어와의 거리에서 1을 뺀 값을 result에 더해줌
    
    // 아기 상어의 크기가 count와 같아졌을 경우 상어 크기 증가 (아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가한다는 조건에 의함)
    if size == count { size += 1; count = 0 }
    
    shark = (fish[0].0, fish[0].1) // 먹은 물고기의 자리로 상어 위치 바꿔줌
}

👉 bfs, 구현 문제로, 주어진 조건을 잘 읽고! 정리하여 풀어야 한다.

한 번의 bfs 함수 실행 시마다 어떤 물고기를 먹는 것이 가장 효율적인지 따지고,
더 이상 먹을 물고기가 없을 경우에 실행을 종료해주었다.

 

[ bfs 함수 ]

• queue에 탐색해야 할 위치들을 추가해주면서 반복이 진행되도록 했는데,
  removeFirst 하지 않고 index 변수를 활용하여 시간 복잡도를 줄였다.
  따라서 while은 큐의 길이가 index보다 짧아지기 전 까지,
  그러니까 더 이상 탐색할 좌표 값이 없을 때까지 반복하도록 해주었다.
• distance라는 2차원 배열은 주어진 n*n 공간과 같은 크기로 생성하고 0으로 채워주었는데,
  아기 상어가 해당 좌표까지 가는데에 걸린 거리를 저장하기 위해 만든 배열이다.
  그리고 함수 중간 예외 처리용 if문을 보면, distance[nx][ny]가 0이 아닐 경우를 예외로 넣었는데,
  이렇게 distance 함수는 이미 그 자리를 지나갔는지 판단할 수 있게 해주는 역할도 한다.
  함수 초반에, distance 배열의 아기 상어의 출발 위치에 1을 넣은 것은
  아직 시작 위치이므로 1만큼 이동하지는 않았지만 이미 지나간 곳임을 표시하기 위함이다.
  따라서 나중에 distance 배열에서 진짜 이동한 거리를 알려면 해당 거리에서 1을 빼줘야 한다.
• while문 안에서는 상하좌우 탐색을 위한 for문을 돌려주었다.
  dx, dy를 이용하여 nx, ny를 찾아 해당 자리를 탐색해주는 방식으로 진행했고,
  해당 좌표가 주어진 공간에서 벗어나거나 이미 탐색했던 자리일 경우는 예외로 빼서 continue 했다.
• 그리고 그 외에는, 탐색할 (nx, ny) 좌표에 먹을 수 있는 물고기가 있는 경우와 없는 경우로 나눴다.
  먹을 물고기가 있는 경우에는 그 물고기에 대한 정보를 fish 배열에 추가한 후 continue 했고,
  먹을 물고기가 없는 경우에는 또 그 자리의 주변 자리들을 탐색해야 하므로 queue에 좌표를 추가했다.
  그리고 두 경우 모두 한 칸 더 이동했으므로, distance 배열을 갱신했다.

=> bfs 함수에서는 현재 아기 상어의 입장에서 최초로 먹을 수 있는 물고기들에 대한 정보를 얻을 수 있다.

 

[ 메인 실행문 ]

• 아기 상어의 초기 위치를 찾아서 shark에 저장했고, 해당 자리는 0으로 바꿔주었다.
• while문을 반볻하며 먹을 물고기를 하나씩 찾아주는 식으로 풀이했다.
  while에서는 각각 fish, distance, queue를 초기화해준 후 bfs를 실행했다.
• bfs 함수의 실행이 끝났을 때 fish 배열이 비어있다면
  공간에 더 이상 먹을 물고기가 없었다는 의미이므로, result 값을 그대로 출력하고 실행을 종료했다.
• fish 배열이 비어있지 않을 경우에는 하나의 물고기를 먹을 수 있다는 의미이므로
  count를 추가해서 하나의 물고기를 먹었다는 것을 표시해준다.
• fish 배열은 문제에서 주어진 조건에 맞게 정렬해준다.
  이번 bfs 실행에서 얻은 정보를 토대로 어떤 물고기를 먹어야 하는지 결정하기 위함이다.
  정렬이 끝나면 fish 배열의 첫 번째 요소에 저장된 물고기가 당첨이다.
  space에서 해당 물고기의 자리는 0으로 바꿔주고, result에 해당 물고기를 먹는 데 걸린  거리를 더했다.
• 만약 아기 상어의 크기가 count와 같아졌다면,
  자신의 크기와 같은 수만큼 물고기를 먹었다는 의미이므로 사이즈를 증가시켜주었다.
• 그리고 마지막으로는 아기 상어의 위치를 해당 물고기가 있던 자리로 옮겨주어
  새로운 반복을 실행할 수 있게 준비한다.

 

💡 피드백

• 정말 정말 어려웠다.ㅜ dfs는 그나마 좀 익숙해진 것 같은데 bfs는 계속 어색한 느낌이다.
  그리고 이건 bfs를 떠나서 완전 빡구현 문제같아서 더 힘들었다.ㅎ
• 조건도 많아서 주어진 조건들을 미리 잘 정리해서 풀어야 하는 문제같다.
• 다시 한 번 꼭 풀어보자..~!~