Swift) 백준 17143번 낚시왕 - G1

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

17143번: 낚시왕

낚시 할때 원본 배열에다가 바로바로 적용하지 말고 초기화된 배열에다가 상어의 위치를 배치 한 후, 원본 배열에다가 적용할 것.

만약 원본 배열에다가 상어의 위치를 바로 배치할 시 다음과 같은 문제가 발생할 수 있다.

이런식으로 상어가 배치 되어 있을때, 빨간색 상어를 가장 먼저 이동시킨다고 가정해보면

그림과같이 푸른 상어는 아직 이동하지도 않았는데, 빨간색 상어가 이동해서 푸른색 상어를 잡아먹거나 잡아 먹힐 수도 있다. 

또한 완전탐색으로 상어를 찾아서 이동시키는 경우 첫번째 행을 탐색 후 두번째행, 세번째 행을 탐색 할때, 이미 이동시킨 빨간색 상어를 다시 이동 시킬수도 있다.

 

따라서

초기화 된 배열을 하나 준비 해둔후

빨간색 상어의 이동 좌표를 계산한 후 초기화 된 배열에 상어를 둔다.

그래서 초록색 상어가 이동해서 빨간색 상어를 잡아먹으면 제대로 된 상어의 격자판 상태를 얻을 수 있다. 

 

그리고 상어의 이동을 반복문으로 처음부터 이동 시킬 시 시간 초과가 나므로, 이동 거리를 최소한으로 줄여야 한다.

상어의 방향이 좌우일때는 (C-1) * 2 만큼 움직이면 원래 위치 원래 방향이 되고, 상하일때는 (R-1) * 2 만큼 움직이면 원래 위치 원래 방향이 된다. 이를 이용해 움직일 거리를 최소한으로 하면 시간초과가 해결 된다.

import Foundation

struct Shark {
    
    enum Direction: Int {
        case on = 1
        case under
        case right
        case left
    }
    
    var i: Int
    var j: Int
    let speed: Int
    var direction: Direction
    
}

let direcMovieCoordi = [(-1, 0), (1,0), (0,1), (0,-1)]

let rcm = readLine()!.split(separator: " ").map { Int($0)! }
let r = rcm[0]
let c = rcm[1]
let m = rcm[2]
var answer = 0

var sharkDict: [Int:Shark] = [:]

var sharkMap: [[Int]] = Array(repeating: Array(repeating: 0, count: c+1), count: r+1)

func printSharkMap() {
    for i in sharkMap {
        print(i.map{"\($0)"}.joined(separator: " "))
    }
}

for _ in 0..<m {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    let sharkI = input[0]
    let sharkJ = input[1]
    let sharkSpeed = input[2]
    let sharkDirec = input[3]
    let sharkSize = input[4]
    sharkDict[sharkSize] = .init(i: sharkI, j: sharkJ, speed: sharkSpeed, direction: .init(rawValue: sharkDirec)!)
    sharkMap[sharkI][sharkJ] = sharkSize
}

func fishing(j: Int) {
    for y in sharkMap.enumerated() {
        if y.element[j] != 0 {
            answer += y.element[j]
            sharkMap[y.offset][j] = 0
            break
        }
    }
}

func moveShark() -> [[Int]] {
    var copyMap = Array(repeating: Array(repeating: 0, count: c+1), count: r+1)
    for y in 1...r {
        for x in 1...c {
            if sharkMap[y][x] != 0 {
                let sharkSize = sharkMap[y][x]
                let shark = sharkDict[sharkSize]!
                var currentSharkCoordi = (shark.i, shark.j)
                sharkMap[currentSharkCoordi.0][currentSharkCoordi.1] = 0
                var moveCoordi = direcMovieCoordi[shark.direction.rawValue-1]
                var direction = shark.direction
                var moveLen = shark.speed
                switch direction {
                case .on, .under:
                    moveLen %= ((r-1)*2)
                case .left, .right:
                    moveLen %= ((c-1)*2)
                }
                
                for _ in 0..<moveLen {
                    let di = currentSharkCoordi.0 + moveCoordi.0
                    let dj = currentSharkCoordi.1 + moveCoordi.1
                    
                    if di < 1 || di > r || dj < 1 || dj > c {
                        if direction.rawValue%2 == 0 {
                            direction = .init(rawValue: direction.rawValue-1)!
                        } else {
                            direction = .init(rawValue: direction.rawValue+1)!
                        }
                        moveCoordi = direcMovieCoordi[direction.rawValue-1]
                        currentSharkCoordi.0 = currentSharkCoordi.0 + moveCoordi.0
                        currentSharkCoordi.1 = currentSharkCoordi.1 + moveCoordi.1
                        continue
                    }
                    
                    currentSharkCoordi.0 = di
                    currentSharkCoordi.1 = dj
                }
                
                
                sharkDict[sharkSize] = .init(i: currentSharkCoordi.0, j: currentSharkCoordi.1, speed: shark.speed, direction: direction)
                if copyMap[currentSharkCoordi.0][currentSharkCoordi.1] != 0 {
                    if sharkSize > copyMap[currentSharkCoordi.0][currentSharkCoordi.1] {
                        copyMap[currentSharkCoordi.0][currentSharkCoordi.1] = sharkSize
                    }
                } else {
                    copyMap[currentSharkCoordi.0][currentSharkCoordi.1] = sharkSize
                }
            }
        }
    }
    return copyMap
}

for fishingMan in 1...c {
    fishing(j: fishingMan)
    sharkMap = moveShark()
}

print(answer)