https://www.acmicpc.net/problem/1018
문제
지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오
접근 방법 / 풀이 과정
우선 NxM 크기의 보드의 N과 M은 8보다 크다.
이 보드를 잘라내어 8x8크기를 가진 체스판을 만들어야한다. 이때 자르는 위치는 아무곳에서 골라도 된다고 한다.
생각해보자, 체스판은 검은색과 흰색이 번갈아가며 칠해져 있다.
문제에서는 맨 왼쪽 위 칸이 흰색인 경우와 검은색인 경우가 있다고 했다.
따라서 앞으로 만들 체스판은 색이 어떻게 되어있든 왼쪽 위칸이 검은색인 체스판과 흰색인 체스판만을 상정하면 될 것이다.
이제 지민이의 보드판이 주어졌을 때 어떤 부분을 잘라야 바꿀 색이 최소가 되는지 알아야한다.
어떻게 최소가 되는지 알 수 있을까? 고민 끝에 떠오른 아이디어는 기존의 체스판과 지민이의 보드판을 대조해보는 것이다. 만약 보드판과 체스판이 겹치는 부분이 많다면 바꿀 부분이 적다는 뜻이고, 겹치는 부분이 적다면 바꿔야할 부분이 많다는 것을 의미한다.
이제 코드로 옮겨보자
package java_test;
import java.io.*;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st =new StringTokenizer(bf.readLine() , " ");
int row = Integer.parseInt(st.nextToken());
int col = Integer.parseInt(st.nextToken());
//2차원 배열
boolean[][] board = new boolean[row][col];
//비교하기 위한 2차원 배열
boolean[][] J = { {true,false,true,false,true,false,true,false} ,
{false,true,false,true,false,true,false,true}
};
int topCount = 0;
int bottomCount = 0;
int log = 1000000;
for(int i =0; i < row; i++) {
char[] input = bf.readLine().toCharArray();
// 흰색이라면 true 검은색이라면 false를 배열에 대입한다
for(int j = 0; j < col; j++) {
board[i][j] = (input[j] == 'W' ? true : false);
}
}
// i는 마지막 행이 1씩 증가하며 대조한다
for(int i = 0; i <= row-8; i++) {
//j는 열이 1씩 증가하며 대조한다
for(int j = 0; j < col-8+1;j++) {
topCount = 0;
bottomCount = 0;
//시작 부분(왼쪽 위 꼭지점)칸이 W일 경우와 B일 경우로 나눈다
for(int z = j; z < 8+j; z++) {
//----왼쪽 위가 W일 때 -------
if(board[i][z] != J[0][z-j])
topCount++;
if(board[i+1][z] != J[1][z-j])
topCount++;
if(board[i+2][z] != J[0][z-j])
topCount++;
if(board[i+3][z] != J[1][z-j])
topCount++;
if(board[i+4][z] != J[0][z-j])
topCount++;
if(board[i+5][z] != J[1][z-j])
topCount++;
if(board[i+6][z] != J[0][z-j])
topCount++;
if(board[i+7][z] != J[1][z-j])
topCount++;
//-----왼쪽 위가 B일 때 ------
if(board[i][z] != J[1][z-j])
bottomCount++;
if(board[i+1][z] != J[0][z-j])
bottomCount++;
if(board[i+2][z] != J[1][z-j])
bottomCount++;
if(board[i+3][z] != J[0][z-j])
bottomCount++;
if(board[i+4][z] != J[1][z-j])
bottomCount++;
if(board[i+5][z] != J[0][z-j])
bottomCount++;
if(board[i+6][z] != J[1][z-j])
bottomCount++;
if(board[i+7][z] != J[0][z-j])
bottomCount++;
}
// 시작칸이 흰색일 때와 검은색일 때를 비교하여 더 작은 값을 log에 담는다
int tmp = (topCount > bottomCount ? bottomCount : topCount);
log = log > tmp ? tmp : log;
}
}
System.out.println(log);
}
}
느낀점 / 배운점
처음에 문제를 잘못 이해하여 잘못된 코드를 작성했었다.
전에도 느꼈지만 문제를 정확히 파악해야 한다. 그래야 좀 더 신속하고 올바른 정답을 작성할 수 있기 때문이다.
