브루트포스 (Brute Force)
브루트 포스를 사전적 의미로 찾아본다면 다음과 같다.- Brute : 무식한
- Force : 힘
즉, 발생하는 모든 경우를 무식하게 탐색한다는 뜻이다. 전체를 탐색한다는 의미에서 전체 탐색이라고도 한다.
브루트포스는 가능한 모든 경우의 수를 시도하면서 정확한 해답을 찾는 방식으로 동작한다. 이는 모든 가능성을 다 검사하기 때문에 정확한 답을 찾을 수 있지만, 경우에 따라서는 비효율적일 수도 있다.
브루트포스는 주로 작은 입력 크기에 대한 문제나 문제의 특성상 다른 최적화 기법들이 적용하기 어려운 겨우에 사용된다. 예를 들어, 모든 순열을 생성하거나 부분집합을 생성하면서 특정 조건을 만족하는 것을 찾는 경우에 브루트 포스가 활용될 수 있다.
이를 활용해 백준 1018번 체스판 다시 칠하기를 풀어보았다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
private static boolean[][] board;
private static int min = 64; //8 * 8 칸이므로 최대 64
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str = br.readLine().split(" ");
int N = Integer.parseInt(str[0]);
int M = Integer.parseInt(str[1]);
board = new boolean[N][M];
for(int i = 0; i < N; i++){
String line = br.readLine();
for(int j = 0; j < M; j++){
if(line.charAt(j) == 'W'){
board[i][j] = true; //W이면 true
}else{
board[i][j] = false;
}
}
}
for(int i = 0; i < N - 7; i++){
for(int j = 0; j < M - 7; j++){
findBoard(i, j);
}
}
System.out.println(min);
}
private static void findBoard(int x, int y){
int end_x = x + 8;
int end_y = y + 8;
//첫번재 칸의 색
boolean TF = board[x][y];
int count = 0;
for(int i = x; i < end_x; i++){
for(int j = y; j < end_y; j++){
if(board[i][j] != TF){
count++;
}
TF = (!TF);
}
TF = (!TF); //체스 칸의 열 또한 흰색 검은색 반복임
}
count = Math.min(count, 64-count);
min = Math.min(count, min);
}
}문제 풀이
체스판을 만들기 위해서 격자에서 8 * 8 크기의 부분의 체스판을 만들어보면서, 최소한의 색칠을 했어야했다. 주어진 체스판에서 가능한 모든 부분을 체스판으로 만들어보면서, 색칠해야하는 최소 값을 구해야했기에 이를 모든 부분에서 비교하여 최소 값을 찾았다.
한 줄에서 첫번째 칸이 검은색이면, 다음 칸은 하얀색, 그 다음 칸은 검은색이어야하며,
그 다음줄에서 첫번째 칸은 흰색, 그 다음 칸은 검은색, 그 다음칸은 흰색이어야한다.
그러므로 하얀색일 경우 true를 검은색일 경우 false로 이차원 배열을 만들고,
이를 계속 바꿔주며 다를 경우 색을 칠하는 count를 더하였다.
마찬가지로 줄이 바뀔 경우 위의 첫번째와 색이 달라야하므로 이부분도 바꿔주었다.
최솟값을 구해야했기에, 1칸만 바꿔야하는 경우도 생각하여야했다. 예를 들면 보드의 맨 첫번째줄 첫번째 칸만 바꾸면 되는 경우도 있기때문에, count와 64 - count 중에서 최솟값을 비교하였다.
