[백준/Swift] 1018 : 체스판 다시 칠하기

안녕하세요~!!

 

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

1018번: 체스판 다시 칠하기

---

간단한 문제 설명 부터 시작하겠습니다!!

M x N 크기의 보드를 잘라 8*8 형태의 체스판을 만든다.

 

이때 체스판의 각 칸은 검(B) or 흰(W) 중 한개로 칠해져 있는데,

변을 공유하는 두개의 사각형은 체스판처럼 다른 색으로 칠해져 있어야 한다.

 

체스판을 만들 때 다시 칠해야 할 최소 칸 개수를 구하는 게 문제입니다.

 

---

처음에 온갖 방법을 썼는데 계속해서 틀렸었습니다. ( 한 5시간 고민했는데,,)

 

그 이유가 이중 포문에서 board를 훑을 때 첫번째 포문을 x 로 한 상태에서 보드를 순회했기 때문입니다..ㅠㅠ;;

(저는 원래 x,y 탐색을 할 때 x를 가로 == x 세로 == y로 두고  탐색을 진행합니다.)

 

다음은 코드입니다!!

 

이번엔 좀 깔끔해 보이게 작성해봤습니다.

 

import Foundation

if let model = inputData(){
    bruteForce(model: model)
    print(model.count)
}


// M x N을 탐색하는 보드의 처음과 끝이 8보다 작다면 다음 줄을 순회하도록 했습니다.
func bruteForce(model : Model){
    for y in 0..<model.height{
        for x in 0..<model.width{
            if model.width - x >= model.minLine && model.height - y >= model.minLine{
                let tmp = drawBoard(x: x, y: y, model: model)
                if tmp < model.count{
                    model.count = tmp
                }
            }else{
                break
            }
        }
    }
}

// 데이터를 입력받습니다.
func inputData() -> Model?{
    if let input = readLine(){
        let nm = input.split(separator: " ").map{Int(String($0))!}
        return Model(width: nm[1], height: nm[0])
    }
    return nil
}

/**
 * 보드의 최소 draw를 탐색하는 함수입니다.
 * 보드의 시작점이 "W" 일때 or "B" 일 때 두 가지의 경우로 나누어
 * W == 0일때 칠해야 할 최소 경우를 aCnt
 * B == 0일 때 칠해야 할 최소 경우를 bCnt로 둔 후 최소값을 반환했습니다.
 */
func drawBoard(x :Int, y: Int, model: Model) -> Int{
    var aCnt = 0
    var bCnt = 0
    for dy in 0..<model.minLine{
        for dx in 0..<model.minLine{
            let ny = dy + y
            let nx = dx + x
            
            // w == 0 일때
            if ((dy + dx) % 2 == 0 && model.board[ny][nx] == "B") ||
                ((dy + dx) % 2 == 1 && model.board[ny][nx] == "W"){
                aCnt += 1
            }
            if ((dy + dx) % 2 == 0 && model.board[ny][nx] == "W") ||
                ((dy + dx) % 2 == 1 && model.board[ny][nx] == "B") {
                bCnt += 1
            }
        }
    }
    return aCnt > bCnt ? bCnt : aCnt;
}


// 자료형들입니다.
class Model {
    
    var width : Int
    var height : Int
    var minLine : Int
    var count : Int
    var board : [[String]]
    
    init(width w: Int , height h: Int){
        width = w
        height = h
        minLine = 8
        count = 9999
        board = Array(repeating: [String](), count: height)
        for i in 0..<height{
            if let line = readLine(){
                board[i] = line.map{String($0)}
            }
        }
    }
}

 

Come to my Github