[baekjoon 1018번] 브루트 포스 - 체스판 다시 칠하기
문제
지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
출력
첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.
예제 입력 1
|
예제 출력 1 1 |
|||
예제 입력 2
|
예제 출력 2 12 |
문제풀이
이번 문제 또한 설명이 굉장히 복잡하기 때문에 간단히 풀어서 설명해보도록 하겠다.
1. 체스판은 무조건 8x8의 형태이며 한 변을 공유하는 두 칸의 색깔은 서로 달라야 한다.(왼쪽이 흰이면 오른쪽은 검)
2. N(세로)xM(가로)의 칸으로 나뉘어진 판에서 8x8 칸만 따로 띄어 놓고 보았을 때 그 칸이 체스판이 되려면 몇몇 개의 칸의 색깔을 바꿔야 한다.
3. 이때 이 색깔을 바꾸는 횟수의 최솟값을 구하여라.
이것이 이 문제의 핵심이다.
그렇다면 이것을 코드로 구현해보겠다.
먼저 입력값을 적절하게 처리하여 받아준다.
그리고 여러가지 변수를 만드는데 모두 필요한 것들이다.
diffCnt는 주어진 판에서 8x8의 체스판이 나올 수 있는 갯수만큼의 크기를 가진 배열이다. 이 배열은 각각의 체스판과의 비교에서 몇 개의 칸을 바꿔야 하는지 저장할 변수이다.
문제에서는 최솟값만을 구하라고 하였으므로 이 배열은 필요가 없지만 나중에 어떠한 값들이 나왔는지 확인하기 위해 생성하였다.
그리고 diffdiffCnt변수는 이름이 좀 그렇긴 하지만 diffCnt의 카운팅 변수이다.
String변수 3개는 각각 위에서부터 왼쪽 제일 위가 흰색일 때의 체스판과 왼쪽 제일 위가 검은색일 때의 체스판, 그리고 입력된 판에서 추출한 체스판 문자열이 담길 변수이다.
incompleteChessBoard를 변수로 쓰는 이유는 체스판을 추출하여 원래의 체스판과 비교하기 때문이다.
그냥 원래 입력값에서 for문을 통하여 하나하나 비교하는 것도 되지만 이 방법이 배열을 이용하는 방법보다 빠르기 때문에 그냥 이렇게 하였다.
그리고 그 밑의 min은 최솟값이 담길 변수이고, tmp1과 tmp2는 각각 입력된 값이 얼마나 많이 바뀌었나를 저장할 임시변수이다. 이 임시변수가 2개인 이유는 밑에서 설명하도록 하겠다.
이번 코드의 핵심 코드이다.
언뜻보면 어려워보이는 코드이지만 실제로는 굉장히 간단한 코드이다.
1. 입력된 판에서 8x8판을 →(가로), ↓(세로) 순으로 추출한다.
2. 추출된 8x8판을 W로 시작하는 체스판, B로 시작하는 체스판과 비교하여 얼마나 다른가 측정한다.
3. 그리고 두 측정값 중 가장 작은 값을 추출하여 실제 min에 들어있는 값과 비교하여 어떤값이 더 작은가 확인한다.
4. 더 작은 값을 배열에 저장하고 배열의 카운팅 변수를 증가시킨다.
5. 1~4를 반복한다.
이 코드에서 보다시피 w로 시작하는 체스판과 b로 시작하는 체스판을 추출된 체스판과 비교하기 때문에 tmp1과 tmp2라는 임시변수가 2개가 쓰인다.
이렇게 2개를 비교하는 이유는 둘 중 하나만 비교했을 때
8 9
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBW
이런 값이 들어올 경우 1가지로만 비교하면 최솟값이 31이 아닌 32가 나올 수 있기 때문이다.
이런 오류를 제거하기 위해 번거롭지만 w로 시작하는, b로 시작하는 체스판과 추출된 체스판을 각각 비교하는 것이다.
테스트 해본 값들
입력 예시 2개
8 8
BBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
출력값: 1
8 9
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBW
출력값: 31
위 코드를 이용하여 최대 50x50판을 입력값으로 넣었을 때 연산시간
평균 0.05초 정도 걸렸었다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
import java.io.*;
public class Main
{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static int chooseChessBoard() throws IOException
{
String[] str = br.readLine().split(" ");
int[] sizeOfChess = {Integer.parseInt(str[0]),Integer.parseInt(str[1])}; //{세로,가로}
String[] chessBoard = new String[sizeOfChess[0]];
for(int i = 0 ; i < sizeOfChess[0] ; i++) {chessBoard[i] = br.readLine();}
int[] diffCnt = new int[(sizeOfChess[0]-8+1)*(sizeOfChess[1]-8+1)];
int diffdiffCnt = 0; // diffCnt의 카운팅 변수
String WcompleteChessBoard = ("WBWBWBWB"+"\n"+"BWBWBWBW"+"\n").repeat(4);
String BcompleteChessBoard = ("BWBWBWBW"+"\n"+"WBWBWBWB"+"\n").repeat(4);
String incompleteChessBoard;
int min = 100; // 최솟값을 저장할 변수
int tmp1,tmp2;
// 세로로 비교하면서 가장 차이가 적은 부분을 찾아냄
for(int i = 0 ; i <= sizeOfChess[0]-8 ; i++)
{
// 가로로 비교하면서 가장 차이가 적은 부분을 찾아냄
for(int j = 0 ; j <= sizeOfChess[1]-8 ; j++)
{
incompleteChessBoard = "";
tmp1=0;
tmp2=0;
// 입력값에서 체스판을 추출함.
for(int k = 0; k < 8 ; k++) {incompleteChessBoard += chessBoard[i+k].substring(j,j+8) + "\n";}
// 완벽한 체스판과 추출한 체스판을 비교함.
for(int l = 0 ; l < 72; l++)
{
if(WcompleteChessBoard.charAt(l) != incompleteChessBoard.charAt(l)) tmp1++;
if(BcompleteChessBoard.charAt(l) != incompleteChessBoard.charAt(l)) tmp2++;
}
// W,B로 시작하는 체스판과 추출한 체스판을 비교함.
diffCnt[diffdiffCnt] = tmp1 < tmp2 ? tmp1 : tmp2;
// 다른 갯수가 최솟값보다 작은지 비교
if(diffCnt[diffdiffCnt] < min) {min = diffCnt[diffdiffCnt];}
diffdiffCnt++;
}
}
return min;
}
public static void main(String args[]) throws IOException {
bw.write(chooseChessBoard()+"");
bw.flush();
bw.close();
}
}
|
cs |
느낀점
이번 문제는 처음부터 설계를 잘못해서 여러가지 반례가 많이 발생한 결과 완벽하게 코드를 작성했다고 생각했지만 완벽하지 않아서 조금 헤맸던 것 같다.
질문 검색에서 여러가지 반례들이 있었기에 풀 수 있었던 문제인 것 같았다.