📔문제
지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다.
하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.
📝입력
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
📺출력
첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.
📝예제 입력 1
8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW📺예제 출력 1
1📝예제 입력 2
10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB📺예제 출력 2
12📝예제 입력 3
8 8
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB📺예제 출력 3
0📝예제 입력 4
9 23
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBW📺예제 출력 4
31📝예제 입력 5
10 10
BBBBBBBBBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBBBBBBBBB📺예제 출력 5
0📝예제 입력 6
8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWWWB
BWBWBWBW📺예제 출력 6
2📝예제 입력 7
11 12
BWWBWWBWWBWW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBWWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW📺예제 출력 7
15🔍출처
-문제를 번역한 사람: baekjoon
-데이터를 추가한 사람: jh05013
-문제를 다시 작성한 사람: jh05013
🧮알고리즘 분류
- 브루트포스 알고리즘
📃소스 코드
import java.util.Scanner;
public class Code1018 {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int N=scanner.nextInt();
int M=scanner.nextInt();
String[][] allBoard=new String[N][M];
int count=(N-8+1)*(M-8+1); //반복 횟수
String whiteLine="WBWBWBWB";
String blackLine="BWBWBWBW";
boolean isNotOnce=true;
String temp="";
for(int i=0;i<N;i++){
temp=scanner.next();
for (int j=0;j<M;j++){
allBoard[i][j]=String.valueOf(temp.charAt(j));
}
}
int start=0;
int line=0;
int min=0;
boolean isOdd=false;
boolean isEven=false;
int color=0;
while(count!=0){
String first="";
//Case 1. 시작이 "B"부터 일 때 최솟값을 확인
first="B";
if(start%2==0){//왼쪽위에가 짝수
isOdd=false;
isEven=true;
}
else{//홀수
isOdd=true;
isEven=false;
}
color = getColor(allBoard, whiteLine, blackLine, start, line, isOdd, isEven, color, first);
int blackColor=color;
color=0;
//Case 2. 시작이 "W"부터 일 때 최솟값을 확인
first="W";
if(start%2==0){//왼쪽위에가 짝수
isOdd=false;
isEven=true;
}
else{//홀수
isOdd=true;
isEven=false;
}
color = getColor(allBoard, whiteLine, blackLine, start, line, isOdd, isEven, color, first);
int whiteColor=color;
int eachMin=0;
if(whiteColor>blackColor){
eachMin=blackColor;
}
else{
eachMin=whiteColor;
}
if(min==0 && isNotOnce){
min=eachMin;
isNotOnce=false;
}
else{
if(min>eachMin){
min=eachMin;
}
}
color=0;
line++;
if(line+7>=M){
line=0;
start++;
if(start+7>=N){
break;
}
}
count--;
}
System.out.println(min);
}
public static int getColor(String[][] allBoard, String whiteLine, String blackLine, int start, int line, boolean isOdd, boolean isEven, int color, String first) {
for(int i = start; i< start +8; i++){
int roopLine=0;
for(int j = line; j< line +8; j++){
if(first.equals("W")){//맨 왼쪽 위 칸이 흰색
if(isEven){//시작 줄 (0.0일 때)
if(i%2==0){//그 행도 짝수면 "W"로 시작
if(!String.valueOf(whiteLine.charAt(roopLine)).equals(allBoard[i][j])){
color++;
}
roopLine++;
}
else{ //"B"로 시작
if(!String.valueOf(blackLine.charAt(roopLine)).equals(allBoard[i][j])){
color++;
}
roopLine++;
}
} else if (isOdd) {//시작 줄 (1,0) "W"
if(i%2==0){//그 다음행 짝수면 "B"로 시작
if(!String.valueOf(blackLine.charAt(roopLine)).equals(allBoard[i][j])){
color++;
}
roopLine++;
}
else{ //"W"로 시작
if(!String.valueOf(whiteLine.charAt(roopLine)).equals(allBoard[i][j])){
color++;
}
roopLine++;
}
}
}
else if(first.equals("B")){ //검정색
if(isEven){//시작 줄 (0.0일 때)
if(i%2==0){//그 행도 짝수면 "B"로 시작
if(!String.valueOf(blackLine.charAt(roopLine)).equals(allBoard[i][j])){
color++;
}
roopLine++;
}
else{ //"B"로 시작
if(!String.valueOf(whiteLine.charAt(roopLine)).equals(allBoard[i][j])){
color++;
}
roopLine++;
}
} else if (isOdd) {//시작 줄 (1,0) "W"
if(i%2==0){//그 다음행 짝수면 "B"로 시작
if(!String.valueOf(whiteLine.charAt(roopLine)).equals(allBoard[i][j])){
color++;
}
roopLine++;
}
else{ //"W"로 시작
if(!String.valueOf(blackLine.charAt(roopLine)).equals(allBoard[i][j])){
color++;
}
roopLine++;
}
}
}
}
}
return color;
}
}
📰출력 결과
📂고찰
엉엉
몇시간에 걸쳐서 겨우 풀었다.
그냥 시작이 W일 때랑, B일때를 계산해보면 됐다..
물론 입력받은 판 값이 W일 때를 나누는 게 아니라, 그냥 W/B로 나누어 계산하고, 둘 중 적은 거를 eachMin에 넣고, 둘 중 작은게 min보다 작으면 그것이 min이 된다. 그다음 계속 반복하는 식으로 풀었다.
자고 일어나자마자 여러번 다시 푼 나..
MySQL DBA 신입 지원