[Swift 알고리즘] 백준 17143 낚시왕

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

17143번: 낚시왕

 

 

해결 방법

1. (row, col)에 상어를 저장

2. 상어라는 데이터 집합체에 (row, col, position, size, speed)를 저장

3. 만약 speed * direction 이 최대로 갈 수 있는 row 혹은 col을 넘겼을 때(n)의 로직

 

 

핵심 로직인 상어를 어떻게 움직일지 고민했습니다. 만약 (curRow, curCol) * speed * direction이 최대 row col을 초과할 때 어떤 로직을 세워야 할 지 고민했습니다. 이를 수직선으로 나타내게 되면

 

ex) row가 4이고 direction은 row + 1, speed 6이라고 가정

(1) 만약 최대 row, col을 초과하게 되면

   (i) 길의 2배수 만큼의 나머지를 구하기 // 왜냐하면, 길의 2배수의 몫은 왔다 갔다 해서 그자리에 멈추기 때문입니다.

   (ii) 만약 현재 위치가 길이보다(n) 크다면 진행 방향은 무조건 반대 방향으로 바뀝니다.

 

예를 들어 보겠습니다. row는 0부터 4까지 가능하고, 현재 상어의 row가 0이고 speed가 6이면, 상어는 6만큼 이동하고 멈출 것 입니다. 상어가 6에 멈췄을 때 4만큼 이동하고 2만큼 되돌아가야 합니다. 그렇기에 "(최대Row(4)) - (현재Row(6) % (최대Row(4))을 하여 값을 보정합니다. 그 후에 direction을 거꾸로 만들어줍니다. 

 

 

 

 

만약 speed * direction 값이 음수일 경우에도 비슷하게 작동합니다. cur = prevRow + speed * direction 로 계산하고 cur은 양수 좌표계와 데깔코마니입니다. 그리고 direction만 거꾸로 만들어주면 됩니다.

 

 

 

 

상어 구조체

struct Shark {
  var row: Int
  var col: Int
  var speed: Int
  var direction: Int
  var curDirection: (Int, Int) { return (directions[direction][0], directions[direction][1]) }
  var size: Int
  init(_ r: Int, _ c: Int, _ s: Int, _ d: Int, _ z: Int) {
    self.row = r
    self.col = c
    self.speed = s
    self.direction = d
    self.size = z
  }
  mutating func move() {
    var curRow = (row + curDirection.0 * speed) % tr
    var curCol = (col + curDirection.1 * speed) % tc
    if (direction == 1 || direction == 2 ) {
      if curRow < 0 {
        curRow = abs(curRow)
        self.direction = direction == 1 ? 2 : 1
      }
      
      if curRow >= R - 1 {
        curRow = (R - 1) - (curRow % (R - 1))
        self.direction = direction == 1 ? 2 : 1
      }
      
    }else if (direction == 3 || direction == 4 ) {
      if curCol < 0 {
        curCol = abs(curCol)
        self.direction = direction == 3 ? 4 : 3
      }
      
      if curCol >= C - 1 {
        curCol = (C - 1) - (curCol % (C - 1))
        self.direction = direction == 3 ? 4 : 3
      }
      
    }
    self.row = curRow
    self.col = curCol
  }
}

 

 

이제 상어시스템에 상어를 저장하면 됩니다. 상어를 어떻게 저장하면 효율적일까 고민하다가 이중배열 이 아닌 Hash로 저장하면 시간복잡도를 줄일 수 있을 것이라 생각했습니다. dictionary에 [Position: [Shar]]로 저장하여 shark를 관리하기로 했습니다. 이렇게 된다면, dictionary에 있는 상어들을 움직일 수도 있게하면서 매번 모든 row col을 뒤지지 않을수 있습니다. 

 

상어가 움직일 수 있게 하는 매서드는 다음과 같습니다. board에서 모든 상어를 불러 newBoard에 append하고 newBoard로 갈아끼워 줍니다. 그 다음 만약 board판에 상어가 두 마리 이상 있다면, 몸집이 큰 상어만 남깁니다.

mutating func moveShark() {
    var newBoard: [Position: [Shark]] = .init()
    board.values.flatMap{$0}.forEach{ shark in
      var shark = shark
      shark.move()
      newBoard[.init(row: shark.row, col: shark.col), default: []].append(shark)
    }
    board = newBoard
  }
  
mutating func removeShark() {
    var newBoard: [Position: [Shark]] = .init()
    board.values.map { sharks -> Shark in
      if sharks.count > 1 {
        let curShark = sharks.max{$0.size < $1.size}!
        return curShark
      }
      return sharks.first!
    }
    .forEach { shark in
      newBoard[.init(row: shark.row, col: shark.col), default: []] = [shark]
    }
    board = newBoard
  }

 

마지막으로 상어를 잡는 로직또한 만들어줍니다.

 

mutating func catchShark(col: Int) {
    for i in 0..<R {
      if let shark = board[.init(row: i, col: col)]?.first {
        res += shark.size
        board[.init(row: i, col: col)] = nil
        return
      }
    }
  }

 

 

다음은 코드 전문입니다.

 

import Foundation

final class FileIO {
   private let buffer:[UInt8]
   private var index: Int = 0

   init(fileHandle: FileHandle = FileHandle.standardInput) {
       
       buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
   }

   @inline(__always) private func read() -> UInt8 {
       defer { index += 1 }

       return buffer[index]
   }

   @inline(__always) func readInt() -> Int {
       var sum = 0
       var now = read()
       var isPositive = true

       while now == 10
               || now == 32 { now = read() } // 공백과 줄바꿈 무시
       if now == 45 { isPositive.toggle(); now = read() } // 음수 처리
       while now >= 48, now <= 57 {
           sum = sum * 10 + Int(now-48)
           now = read()
       }

       return sum * (isPositive ? 1:-1)
   }

   @inline(__always) func readString() -> String {
       var now = read()

       while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시

       let beginIndex = index-1

       while now != 10,
             now != 32,
             now != 0 { now = read() }

       return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
   }

   @inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
       var now = read()

       while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시

       let beginIndex = index-1

       while now != 10,
             now != 32,
             now != 0 { now = read() }

       return Array(buffer[beginIndex..<(index-1)])
   }
}

let file = FileIO()
let directions = [[], [-1, 0], [1, 0], [0, 1], [0, -1]]
let (R, C, M) = (file.readInt(), file.readInt(), file.readInt())
let tr = 2 * (R - 1)
let tc = 2 * (C - 1)

struct Shark {
  var row: Int
  var col: Int
  var speed: Int
  var direction: Int
  var curDirection: (Int, Int) { return (directions[direction][0], directions[direction][1]) }
  var size: Int
  init(_ r: Int, _ c: Int, _ s: Int, _ d: Int, _ z: Int) {
    self.row = r
    self.col = c
    self.speed = s
    self.direction = d
    self.size = z
  }
  mutating func move() {
    var curRow = (row + curDirection.0 * speed) % tr
    var curCol = (col + curDirection.1 * speed) % tc
    if (direction == 1 || direction == 2 ) {
      if curRow < 0 {
        curRow = abs(curRow)
        self.direction = direction == 1 ? 2 : 1
      }
      
      if curRow >= R - 1 {
        curRow = (R - 1) - (curRow % (R - 1))
        self.direction = direction == 1 ? 2 : 1
      }
      
    }else if (direction == 3 || direction == 4 ) {
      if curCol < 0 {
        curCol = abs(curCol)
        self.direction = direction == 3 ? 4 : 3
      }
      
      if curCol >= C - 1 {
        curCol = (C - 1) - (curCol % (C - 1))
        self.direction = direction == 3 ? 4 : 3
      }
      
    }
    self.row = curRow
    self.col = curCol
  }
}

struct Position: Hashable {
  var row: Int
  var col: Int
}

struct SharkSystem {
  var board: [Position: [Shark]] = .init()
  var res: Int = 0
  init() { }
  mutating func start() {
    addShark(M)
    for col in 0..<C {
      catchShark(col: col)
      moveShark()
      removeShark()
    }
  }
  
  mutating func addShark(_ count: Int) {
    (0..<count).forEach { _ in
      let curShark: Shark = .init(file.readInt() - 1, file.readInt() - 1, file.readInt(), file.readInt(), file.readInt())
      board[.init(row: curShark.row, col: curShark.col), default: []].append(curShark)
    }
  }
  
  mutating func catchShark(col: Int) {
    for i in 0..<R {
      if let shark = board[.init(row: i, col: col)]?.first {
        res += shark.size
        board[.init(row: i, col: col)] = nil
        return
      }
    }
  }
  mutating func moveShark() {
    var newBoard: [Position: [Shark]] = .init()
    board.values.flatMap{$0}.forEach{ shark in
      var shark = shark
      shark.move()
      newBoard[.init(row: shark.row, col: shark.col), default: []].append(shark)
    }
    board = newBoard
  }
  
  mutating func removeShark() {
    var newBoard: [Position: [Shark]] = .init()
    board.values.map { sharks -> Shark in
      if sharks.count > 1 {
        let curShark = sharks.max{$0.size < $1.size}!
        return curShark
      }
      return sharks.first!
    }
    .forEach { shark in
      newBoard[.init(row: shark.row, col: shark.col), default: []] = [shark]
    }
    board = newBoard
  }
}

var system = SharkSystem()
system.start()
print(system.res)