[프로그래머스][Swift] 퍼즐 조각 채우기 - Level3

 

퍼즐 조각 채우기 [문제 링크]

간단한 문제 요약

 

게임 보드안 빈 공간에, table에 있는 퍼즐을 적절히 올려놓아야한다. 특정한 퍼즐을 놓을 때 주변 빈 공간이 없어야한다. 퍼즐 조각은 회전시킬수있지만 뒤집을 수는 없다. 가장 많이 채웠을때 총 몇칸을 채울 수 있는가?

문제 접근

이 문제를 풀기 위해선 퍼즐을 회전하는 방법을 알아야 합니다.

var board = ... // n*n 2차원 배열

var temp = Array(repeating: Array(repeating: 0, count: n), count: n)
for y in 0..<n {
  for x in 0..<n {
   temp[x][n-1-y] = temp[y][x]
  }
}

 

이 경우는 n*n일때 2차원배열의 모든 원소들을 90도 회전할 때 사용됩니다.

 

 

저는 근데 좌표 회전 방법을 사용했습니다.

A(a,b) -> A'(-b,a)

이는 한 좌표에 대해서 원점을 중심으로 90도 회전한 점을 표기할 수 있습니다. (4번 반복하면 원래 a,b 좌표가 나옴)

 

그리고 저는 블럭을 n*n 형식으로 변환할까 생각하다가. 그냥 블럭을 표시하는 좌표들에 대해서, 전부 최소 좌표 기준으로 비교할수있게 작업을 했고 + 제가 원하는 방식으로 좌표들을 소팅해서 보드에 놓일 수 있는 블럭 좌표들과 table에 있는 블럭들의 좌표들을 얻어서, 놓을 수 있는 블럭을 회전하며, 일치하는 좌표리스트인지를 파악 후 대입하도록 했습니다.

 

 

이렇게 보드의 x,y 좌표에 주황색 영역의 빈 공간이 있다면 이 공간들을 bfs로 탐색한 후에 ( 이때 조건은 해당 칸의 값이 0일때! ) 이 리스트중 가장 작은 값을 중심으로 전부 빼줍니다 !! 이렇게 game board에 있는 빈 공간들을 bfs탐색하면서 비어있는 영역을 bfs탐색하고 하나의 블럭으로 봅니다. 이때 좋은점은 table에서 특정 퍼즐을 가져다 놓았을때 부가적으로 빈 공간이 있는가?를 비교하지 않아도 됩니다.

 

 

table 에 있는 퍼즐들 도 마찬가지로 이렇게 bfs탐색하며 블럭 리스트를 만듭니다. 이때 블럭을 표시하는 값은 1입니다. 그래서..

 

이렇게 보드와 searchCondition을 매개변수로했고, bfs탐색은 특정 board가 원하는 search condition에 따라 0을 탐색해야할지, 또는 1을 탐색해야할지 이렇게 선언했습니다!

 

그래서 table안에 블럭들도 탐색해서 가장 작은 좌표값을 기준으로 뺀 다음에, 제가 원하는 방식으로 소팅을 합니다.

 

 

이제 좌표평면에서 좌표를 90도 이동하는 방식 (x,y ) -> (y,-x) 적용해 퍼즐블럭들을 4번 회전을 수행하면서 보드의 빈 영역의 정규화된 좌표값들과 일치하는지를 검사해나가면서 풀었습니다.

 

어렵네요...

 

코드

 

struct Point: Hashable {
  var x: Int
  var y: Int
  init(_ x: Int, _ y: Int) {
    self.x = x
    self.y = y
  }
}

typealias BlockPoints = [Point]
let directions: [Point] = [(0,1),(0,-1),(-1,0),(1,0)].map { .init($0.0, $0.1) }

func solution(_ game_board:[[Int]], _ table:[[Int]]) -> Int {
  var gameBoard = game_board
  var table = table
  let n = table.count
  var emptyBlocks: [BlockPoints] = []
  
  /// 게임블럭에서 빈 공간 찾기!! 이때 탐색 조건은 보드에서 값이 0인 경우 찾긔
  for y in 0..<n {
    for x in 0..<n where gameBoard[y][x] == 0 {
      let blockPoints = bfs(Point(x, y), in: gameBoard, searchCondition: { $0 == 0 })
      emptyBlocks.append(normalize(blockPoints))
      blockPoints.forEach { gameBoard[$0.y][$0.x] = 1 }
    }
  }
  
  /// table에서 퍼즐 블럭들 찾기. 이때 탐색 조건은 보드에서 값이 1인경우
  var pieceBlocks: [BlockPoints] = []
  for y in 0..<n {
    for x in 0..<n where table[y][x] == 1 {
      let blockPoints = bfs(Point(x, y), in: table, searchCondition: { $0 == 1 })
      pieceBlocks.append(normalize(blockPoints))
      blockPoints.forEach { table[$0.y][$0.x] = 0 }
    }
  }
  
  /// 비어있는 블럭들 하나하나에 대해서, 이제 퍼즐 블럭을 A(x,y) -> A'(y,-x) 90도 회전한 후에 
  /// 최소좌표와 비교했을때 일치하는지를 찾아나가면서 정확히 일치하는 좌표리스트가 있을 경우 놓인것으로 간주!
  /// 이때 내가 원하는 방식으로 좌표들이 소팅되어있어야함.
  var filledCount = 0
  for piece in pieceBlocks {
    for rotation in 0..<4 {
      let rotatedPiece = rotate(piece, rotation)
      if let index = emptyBlocks.firstIndex(where: { $0 == rotatedPiece }) {
        filledCount += rotatedPiece.count
        emptyBlocks.remove(at: index)
        break
      }
    }
  }
  
  return filledCount
}

func rotate(_ points: BlockPoints, _ times: Int) -> BlockPoints {
  var result = points
  for _ in 0..<times {
    let maxX = result.max(by: { $0.x < $1.x })!.x
    result = result.map { Point(maxX - $0.y, $0.x) }
  }
  return normalize(result)
}


/// 가장 작은 x,y값을 기준으로 모든 좌표들을 평탄화함
func normalize(_ points: BlockPoints) -> BlockPoints {
  let minX = points.min(by: { $0.x < $1.x })!.x
  let minY = points.min(by: { $0.y < $1.y })!.y
  return points.map { Point($0.x - minX, $0.y - minY) }.sorted(by: { $0.x == $1.x ? $0.y < $1.y : $0.x < $1.x })
}

func bfs(_ start: Point, in board: [[Int]], searchCondition: (Int) -> Bool) -> BlockPoints {
  let n = board.count
  var visited = Array(repeating: Array(repeating: false, count: n), count: n)
  visited[start.y][start.x] = true
  var queue: [Point] = [start]
  var index = 0
  while index < queue.count {
    let current = queue[index]
    index += 1
    for direction in directions {
      let next = Point(current.x + direction.x, current.y + direction.y)
      if isOutOfBounds(next, n: n) || visited[next.y][next.x] || !searchCondition(board[next.y][next.x]) { continue }
      visited[next.y][next.x] = true
      queue.append(next)
    }
  }
  return queue
}
func isOutOfBounds(_ p: Point, n: Int) -> Bool { !((0..<n)~=p.x && (0..<n)~=p.y) }