백준 17143번 낚시왕 - 스위프트(Swift) 풀이 + 그림 설명

---

 

1. 모든 상어를 순회하면서 현재 열에서 가장 가까운 상어를 잡는다.
2. 모든 상어를 순회하면서 각 상어를 O(1)에 이동시킨다.
3. 상어들을 이동시킬 때 딕셔너리를 이용해서 위치가 중복되면 가장 큰 상어만 남긴다.

 

1. 모든 상어를 순회하면서 현재 열에서 가장 가까운 상어를 잡는다.

 먼저 한 열 오른쪽으로 이동한 뒤 상어를 잡는다. 잡아야 할 상어는 모든 상어를 순회해서 결정한다. 한번 상어를 잡을 때 O(RC)의 시간복잡도가 든다.

 

2. 모든 상어를 순회하면서 각 상어를 O(1)에 이동시킨다.

 s가 최대 1,000까지 가능하다. 1,000칸을 시뮬레이션으로 모두 이동시킬 경우 상어 이동에만 O(1000*RC)의 시간 복잡도가 들게 되어 시간 초과가 발생한다. 각 상어를 O(1)에, 즉 모든 상어 이동을 O(RC)에 처리해야 한다.

 상어의 이동 규칙을 살펴보자. 하늘색 칸에 오른쪽으로 이동하는 상어가 있다고 하면, 2 X (C-1) = 6칸을 이동하면 다시 제자리로 돌아온다. 따라서 s칸 이동 시뮬레이션을 s % (2 X (C-1))칸 이동 시뮬레이션으로 줄일 수 있다.

 여기에서 더 시뮬레이션 이동량을 줄일 수 있다. 남은 이동 칸이 s % (2 X (C-1))칸이므로, 남은 이동은 다음 두 가지 중 하나가 된다.

1. 되돌아오는 일 없이 주어진 방향으로 직진하고 끝
2. 직진 후 되돌아와서 반대 방향으로도 더 직진하고 끝

따라서 일단 주어진 방향으로 최대한 보내고, 더 이동해야 하는 양이 남아있으면 방향을 반대로 꺾어서 남은 이동 해주기, 이렇게 2번의 연산만 해주면 된다.

 

3. 상어들을 이동시킬 때 딕셔너리를 이용해서 위치가 중복되면 가장 큰 상어만 남긴다.

상어의 위치가 겹칠 경우 가장 큰 상어가 나머지 상어를 잡아먹는다는 규칙이 있다. 따라서 모든 상어 이동을 끝낸 뒤에 이 규칙 처리를 해주어야 한다.

 모든 상어를 순회하면서 dict[pos] = shark형태로 저장해준다. 만약 이미 dict[pos] 값이 존재할 경우, pos에 상어가 존재한다는 뜻이므로 현재 상어와 이미 존재하는 상어를 비교해서 큰 상어만 남기고 작은 상어는 죽음 처리를 해준다. 딕셔너리를 사용하므로 이 과정에도 O(RC)이 들게 된다.

 전체 시간복잡도를 구해보면, 일단 모든 열을 순회하는 데에 O(C), 상어 잡기와 이동에 O(RC)가 들기 때문에 총 시간복잡도는 O(RC^2)이다.

반응형

---

import Foundation

var R = 0, C = 0, M = 0
var sharks = [Shark]()

enum Direction: Int {
    case up = 1, down, right, left
}

class Shark: CustomStringConvertible {
    var r: Int
    var c: Int
    let s: Int
    var d: Direction
    let z: Int
    var dead: Bool = false
    
    var pos: Int {
        return C * r + c
    }
    
    init(r: Int, c: Int, s: Int, d: Int, z: Int) {
        self.r = r
        self.c = c
        self.s = s
        self.d = Direction(rawValue: d)!
        self.z = z
    }
    
    func move() {
        var dist: Int
        
        switch d {
        case .up, .down:
            dist = s % (2 * (R - 1))
        case .right, .left:
            dist = s % (2 * (C - 1))
        }
        
        while dist > 0 {
            switch d {
            case .up:
                let goStraight = min(r, dist)
                r -= goStraight
                dist -= goStraight
                
                if r == 0 {
                    d = .down
                    r = 2
                }
            case .down:
                let goStraight = min(R+1-r, dist)
                r += goStraight
                dist -= goStraight
                
                if r == R + 1 {
                    d = .up
                    r = R - 1
                }
            case .right:
                let goStraight = min(C+1-c, dist)
                c += goStraight
                dist -= goStraight
                
                if c == C + 1 {
                    d = .left
                    c = C - 1
                }
            case .left:
                let goStaright = min(c, dist)
                c -= goStaright
                dist -= goStaright
                
                if c == 0 {
                    d = .right
                    c = 2
                }
            }
        }
    }
    
    var description: String {
        return ("(\(r), \(c)), \(dead ? "Dead": "Live")")
    }
}

func catchShark(col: Int) -> Int {
    var target: Shark?
    
    for shark in sharks {
        guard !shark.dead && shark.c == col else { continue }
        
        if target == nil {
            target = shark
        } else {
            if target!.r > shark.r { target = shark }
        }
    }
    
    target?.dead = true
    
    return target?.z ?? 0
}

func moveAllSharks() {
    var dict = [Int:Shark]()
    
    for shark in sharks {
        guard !shark.dead else { continue }
        
        shark.move()
        
        if let existingShark = dict[shark.pos] {    // 해당 자리에 다른 상어가 있으면
            if existingShark.z < shark.z {
                dict[shark.pos] = shark
                existingShark.dead = true           // 작은 상어는 잡아 먹힘
            } else {
                shark.dead = true
            }
        } else {
            dict[shark.pos] = shark
        }
    }
}

func solution() {
    var input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    R = input[0]
    C = input[1]
    M = input[2]
    
    for _ in 0..<M {
        input = readLine()!.split(separator: " ").map{ Int(String($0))! }
        let r = input[0]
        let c = input[1]
        let s = input[2]
        let d = input[3]
        let z = input[4]
        
        let shark = Shark(r: r, c: c, s: s, d: d, z: z)
        sharks.append(shark)
    }
    
    var sum = 0
    
    for col in 1...C {
        sum += catchShark(col: col)
        moveAllSharks()
    }
    
    print(sum)
}

solution()