[백준/Swift] 20056번: 마법사 상어와 파이어볼

 

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

20056번: 마법사 상어와 파이어볼

 

굉장히 많은 시행착오를 겪은 문제...

 

구현 방법(흐름)

fireBalls 배열에는 현재 존재하는 파이어볼을 넣어놓는 배열 [FireBall]

array에는 어떤 좌표값에 파이어볼을 넣어놓는 배열

→ ex) (2, 3) 위치에 FireBall() 객체 넣어놓는다

---

k번 반복

1. 파이어볼 이동이동한 좌표를 기준으로 array 배열에 파이어볼 넣기
2. 현재 파이어볼을 넣어놓은 fireBalls 배열을 순회하면서 파이어볼 이동시키기.
3. 2개 이상 파이어볼은 합쳐져 4개로 나누기→ flatMap 함수를 통해 합칠 수 있음 (nil 제외해 줌)
4. 합쳐진 파이어볼 배열들을 순회하면서 한 좌표에서 4개의 파이어볼 나누기
5. array의 같은 좌표에 있는 파이어볼을 하나의 배열 원소로 합치기

---

첫 번째 시도

array에 해당 위치에 파이어볼이 몇 개 있는지 카운팅. 

array 전체를 돌면서 파이어볼이 2개 이상 있는 좌표에서 → 파이어볼을 저장해 둔 fireBalls에 해당 좌표에 위치하는 파이어볼을 찾아 진행

→ 시간초과 발생 🚨

 

바뀐 구현 방법 ⬇️

2차원 배열 array에 파이어볼 값 넣기 → filter 고차 함수로 파이어볼 2개 이상인 곳만 걸러내서 mergeList 만들기

→ [[], [], [], []] 이런 식으로 같은 좌표에 있는 파이어볼이 하나의 배열 원소로 들어감

mergeList 순회하며 4개의 파이어볼로 나누기: array[x][y]를 4개의 파이어볼로 바꾸기

모든 mergeList 순회가 끝나면 fireBalls에 파이어볼들 넣어주기

array.flatMap{$0}.flatMap{$0} → 3차원 배열을 1차원 배열로 압축 (nil 제외)

 

import Foundation

let directions = [[-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1]]
struct FireBall {
    let r: Int
    let c: Int
    let mass: Int
    let speed: Int
    let direction: Int
    
    func move(n: Int) -> Self {
        var nr = (directions[direction][0] * speed + r) % n
        var nc = (directions[direction][1] * speed + c) % n
        if nr < 0 { nr += n } //왼쪽으로 넘어가면 n을 더해주면 된다
        if nc < 0 { nc += n }
        return FireBall(r: nr, c: nc, mass: mass, speed: speed, direction: direction)
    }
}

//input
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = input[0]
let m = input[1]
let k = input[2]
var fireBalls = [FireBall]()
var array = Array(repeating: Array(repeating: [FireBall](), count: n), count: n)

for _ in 0..<m {
    let fireball = readLine()!.split(separator: " ").map{ Int(String($0))! }
    fireBalls.append(FireBall(r: fireball[0]-1, c: fireball[1]-1, mass: fireball[2], speed: fireball[3], direction: fireball[4]))
}

func move() {
    // 1. 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.
    fireBalls = fireBalls.map{$0.move(n: n)}
    array = Array(repeating: Array(repeating: [FireBall](), count: n), count: n)
    fireBalls.forEach { fireball in
        array[fireball.r][fireball.c].append(fireball)
    }
}

// 2. 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
func merge() {
    //filter 고차 함수로 파이어볼 2개 이상인 곳만 걸러내서 mergeList 만들기 → [[], [], [], []] 이런 식으로 같은 좌표에 있는 파이어볼이 하나의 배열 원소로 들어감
    let fireBallsInSameRoom = array.flatMap{$0}.filter{ $0.count >= 2 }
    
    for fireballs in fireBallsInSameRoom {
        let x = fireballs.first!.r
        let y = fireballs.first!.c
        var isEven = false
        var isOdd = false
        var mass = 0
        var speed = 0
        
        for fireball in fireballs {
            if fireball.direction % 2 == 0 { isEven = true }
            else { isOdd = true }
            mass += fireball.mass
            speed += fireball.speed
        }
        mass /= 5
        speed /= fireballs.count
        
        if mass == 0 {
            array[x][y] = []
            continue
        }
        
        //4개의 파이어볼로 나눠서 (x,y)좌표에 업데이트 (추가x 4개만 해당 좌표에 있는 것)
        let ballsDirection = isEven && isOdd ? [1,3,5,7] : [0,2,4,6]
        array[x][y] = ballsDirection.map{FireBall(r: x, c: y, mass: mass, speed: speed, direction: $0)} //ballsDirection 배열을 map으로 순회하면서 차례로 FireBall 객체에 파라미터 값으로 넣어줌
    }
    
    //update fireBalls
    fireBalls = array.flatMap{$0}.flatMap{$0} //3차원 배열을 1차원 배열로 압축 (nil 제외)
}

for _ in 0..<k {
    move()
    merge()
}

print(fireBalls.reduce(0, { partialResult, fireball in
    partialResult + fireball.mass
}))

 

무수히 많은 노력의 흔적.. 런타임 에러 환장합니다. 대체 어디서..?

 

 

사실 도저히 시간초과의 늪에서 빠져나오질 못해 다른 분의 코드를 확인했습니다…! 안에 들어간 구현 방법은 동일했으나

“배열을 어떤 식으로 활용할지”, “내장 메소드를 효과적으로 간편하게 구현”, “구조체 활용(특히 메소드)”

하는 부분에서 시간 효율성이 달라졌던 것 같습니다. 그래도 이 분의 코드 덕분에 알고만 있었고 잘 사용하지 않았던 flatMap 고차 함수를 다음에 사용해 보겠다는 다짐을..!! 간편하고 좋을 거 같네요.

눈물이 앞을 가립니다 흑흑💦

 

다시 한번 복습하며 포스팅 마치겠습니다.

 

 

 

[참고]

https://velog.io/@aurora_97/%EB%B0%B1%EC%A4%80-20056%EB%B2%88-%EB%A7%88%EB%B2%95%EC%82%AC-%EC%83%81%EC%96%B4%EC%99%80-%ED%8C%8C%EC%9D%B4%EC%96%B4%EB%B3%BC-Swift

백준 20056번: 마법사 상어와 파이어볼 - Swift