풀이1
실버5 : 브루트포스 문제이다.
Code
//
// main.swift
// CodingTest
//
// Created by 최완식 on 2021/08/15.
//
import Foundation
let chessSize = 8
func calcFillCount(_ board: [[String]], with color: String, other: String) -> Int {
var count = 0
let colorDic = [0: color, 1: other]
for i in 0..<chessSize {
for j in 0..<chessSize {
let nowColor = colorDic[(i + j) % 2]!
if board[i][j] != nowColor {
count += 1
}
}
}
return count
}
func getMinimumFillCount(_ board: [[String]]) -> Int {
let startWithBlackCount = calcFillCount(board, with: "B", other: "W")
let startWithWhiteCount = calcFillCount(board, with: "W", other: "B")
return min(startWithBlackCount, startWithWhiteCount)
}
func main() {
// 좌상, 우하를 가져온다.
// 해당 부분 체스판을 넣어서 계산을 수행한다.
// min 값을 업데이트 한다.
let seps = readLine()!.split(separator: " ").map { Int($0)! }
let n = seps[0], m = seps[1]
var board = [[String]]()
for _ in 0..<n {
board.append(readLine()!.map { String($0) })
}
var minFillCount = 50*50+1
for i in 0...n-chessSize {
for j in 0...m-chessSize {
let sy = i, sx = j, ey = i+chessSize, ex = j+chessSize
let slicedBoard = board[sy..<ey].map { Array($0[sx..<ex]) }
let count = getMinimumFillCount(slicedBoard)
minFillCount = min(minFillCount, count)
}
}
print(minFillCount)
}
main()
풀이2
실버5 : 완전 탐색 문제이다.
대표적인 완전 탐색 문제이다. 체스판이 될 수 있는 모든 경우에 대해서 몇번의 flip을 해야하는지 세고, 이를 갱신해주면 풀린다. 이 때, 체스판의 규칙을 잘 파악하는 것이 중요하다.
Example
||1|2|3|4|5|6|7|8| |::|:|:|:|:|:|:|:|:| |1|W|B|W|B|W|B|W| B| |2| B|W|B|W|B|W|B|W| |3|W|B|W|B|W|B|W|B| |4|B|W|B|B|B|W|B|W| |5|W|B|W|B|W|B|W|B| |6|B|W|B|W|B|W|B|W| |7|W|B|W|B|W|B|W|B| |8|B|W|B|W|B|W|B|W|
1행에서, 맨 마지막인 8열은 B이고, 그 다음 행의 첫번째는 B이다. 계속해서 엇갈려서 발생하는 것이 아니고, 행이 끝날 때, 마지막 요소가 다음 요소가 된다. 또한 추가적으로 체스판은 시작 위치의 표식이 어떤 것이냐에 따라 모양이 정해진다. 이 부분에서 생각할 수 있는 것은, 같은 모양이나 시작 위치의 표식만 바뀐다. 라는 것이다.
구현
이 것을 구현하기 위한 단계를 생각해보자.
- 우리는 체스판의 크기에 따라 몇 개의 작은 체스판을 조사해야 하는지 정해야 한다.
- 그 안에 들어갔을 때, 시작 위치의 표식을 설정해 주어야 한다.
- 체스판을 만들 수 있는 방법을 진행하며 다른 부분을 체크하고 count 해야한다.
Code
// 실버5 : 백준 1018번 체스판 다시 칠하기
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool map[50][50];
int N, M;
int ans = 2000000000;
void go(int y, int x){
// 각각의 작은 체스판에서 시작 위치의 표식을 W, B으로 설정한다.
// bool으로 잡았기 때문에 0 또는 1로 모델링이 가능하다.
for (int mode = 0; mode <= 1; mode++) {
int localAns = 0;
for (int i = y; i < y+8; i++) {
// 이 부분이 행이 끝났을 떄 표식을
// 다음행에 가져가도록 하는 코드이다.
mode = !mode;
for (int j = x; j < x+8; j++) {
if (mode != map[i][j]) {
localAns++;
}
mode = !mode;
}
}
// 각각에 대해 ans를 업데이트 해준다.
ans = min(ans, localAns);
}
}
int main(){
cin >> N >> M;
// 1, 0으로 바꿔서 넣어주었다. W = 1, B = 0
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
char temp;
cin >> temp;
if (temp == 'W') map[i][j] = 1;
else map[i][j] = 0;
}
}
// 체스판 모양에 따라 발생할 수 있는
// 작은 체스판의 시작 위치를 결정한다.
for (int i = 0; i <= N-8; i++) {
for (int j = 0; j <= M-8; j++) {
go(i, j);
}
}
cout << ans <<'\n';
}