[완전 탐색] 백준 실버4 1018번: 체스판 다시 칠하기(Swift)

 

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

1018번: 체스판 다시 칠하기

풀이과정

위 문제는 검정색(B)과 흰색(W)이 무작위로 색칠되어 있는 체스판을 8x8로 잘라 올바르게 다시 색을 칠할 때 칠해야 하는 정사각형의 최소 개수를 출력하는 문제이다.

위 조건에 올바른 체스판의 경우는 두 가지이다.

왼쪽 상단이 W로 시작하는 체스판과

B로 시작하는 체스판이다.

두 올바른 체스판과 임의로 잘라낸 8x8의 체스판과 비교하여 색이 다른 정사각형의 수를 찾으면 된다.

let board1: [[Character]] = [["W","B","W","B","W","B","W","B"],
                             ["B","W","B","W","B","W","B","W"],
                             ["W","B","W","B","W","B","W","B"],
                             ["B","W","B","W","B","W","B","W"],
                             ["W","B","W","B","W","B","W","B"],
                             ["B","W","B","W","B","W","B","W"],
                             ["W","B","W","B","W","B","W","B"],
                             ["B","W","B","W","B","W","B","W"]]

let board2: [[Character]] = [["B","W","B","W","B","W","B","W"],
                             ["W","B","W","B","W","B","W","B"],
                             ["B","W","B","W","B","W","B","W"],
                             ["W","B","W","B","W","B","W","B"],
                             ["B","W","B","W","B","W","B","W"],
                             ["W","B","W","B","W","B","W","B"],
                             ["B","W","B","W","B","W","B","W"],
                             ["W","B","W","B","W","B","W","B"]]

위처럼 올바른 두 체스판을 이중 배열을 통해 만들어준다.

이후 탐색을 통해 8x8 체스판을 결정하고, 위 board와 비교하여 최솟값을 찾아 result에 저장한다.

최종코드

let nm = readLine()!.split(separator: " ").map { Int($0)! }

let n = nm[0]
let m = nm[1]

let board1: [[Character]] = [["W","B","W","B","W","B","W","B"],
                             ["B","W","B","W","B","W","B","W"],
                             ["W","B","W","B","W","B","W","B"],
                             ["B","W","B","W","B","W","B","W"],
                             ["W","B","W","B","W","B","W","B"],
                             ["B","W","B","W","B","W","B","W"],
                             ["W","B","W","B","W","B","W","B"],
                             ["B","W","B","W","B","W","B","W"]]

let board2: [[Character]] = [["B","W","B","W","B","W","B","W"],
                             ["W","B","W","B","W","B","W","B"],
                             ["B","W","B","W","B","W","B","W"],
                             ["W","B","W","B","W","B","W","B"],
                             ["B","W","B","W","B","W","B","W"],
                             ["W","B","W","B","W","B","W","B"],
                             ["B","W","B","W","B","W","B","W"],
                             ["W","B","W","B","W","B","W","B"]]


var chessboard = [[Character]]()

for _ in 0..<n {
  let y = readLine()!
  chessboard.append(Array(y))
}

var result = Int.max

for y in 0...(n - 8)  {
  for x in 0...(m - 8) {
    var count1 = 0, count2 = 0
    for i in y..<(y + 8) {
      for j in x..<(x + 8) {
        if chessboard[i][j] != board1[i - y][j - x] {
          count1 += 1
        }
        if chessboard[i][j] != board2[i - y][j - x] {
          count2 += 1
        }
      }
    }
    result = min(result, count1, count2)
  }
}

print(result)