곽로그
[백준 1018 자바] 체스판 다시 칠하기 본문
반응형
문제
1018번: 체스판 다시 칠하기
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
www.acmicpc.net
접근
"이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다" 에서 힌트를 얻었다.
"크기가 N, M인 보드에서 8*8 체스판이 될 수 있는 체스판의 시작점"을 이중 for문을 이용해서 구한다. 구한 시작점을 시작으로 8*8의 체스판을 만들고, 이 체스판과 시작점이 B인 8*8인 체스판, 시작점이 W인 8*8인 체스판과 각각 비교를 한다. 다른 칸의 개수가 최소인 것을 구한다. 이렇게 순회를 해서 구한 최소값들 중 최소값을 구한다.
그림으로 설명하면
1. B로 시작하는 체스판, W로 시작하는 체스판을 만든다
2. 지민이가 찾은 보드판에서 8*8 체스판의 시작점이 될 수 있는 것을 찾는다.
N-8, M-8
3. 시작점에서 8*8인 정사각형을 구한다. (ex. 1행 3열)
4. 3에서구한 정사각형과 B로 시작하는 체스판과 비교한다.
5. 3에서 구한 정사각형과 W로 시작하는 체스판과 비교한다.
6. 4,5중 최소값을 구한다.
7. 2에서 찾은 시작점에서 각각 최소값을 구한다음, 이 중에서 최소값을 출력한다.
코드
package bruteforce;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Chess {
public static String[][] square;
public static String[][] squareB
= {{"B","W","B","W","B","W","B","W"},{"W","B","W","B","W","B","W","B"},
{"B","W","B","W","B","W","B","W"},{"W","B","W","B","W","B","W","B"},
{"B","W","B","W","B","W","B","W"},{"W","B","W","B","W","B","W","B"},
{"B","W","B","W","B","W","B","W"},{"W","B","W","B","W","B","W","B"}};
public static String[][] squareW
= {{"W","B","W","B","W","B","W","B"},{"B","W","B","W","B","W","B","W"},
{"W","B","W","B","W","B","W","B"},{"B","W","B","W","B","W","B","W"},
{"W","B","W","B","W","B","W","B"},{"B","W","B","W","B","W","B","W"},
{"W","B","W","B","W","B","W","B"},{"B","W","B","W","B","W","B","W"}};
public static int isRight(int row, int column) {
int countB = 0;
int countW = 0;
int yB=0;
int xB=0;
int yW=0;
int xW=0;
for(int i =row ; i < row+8 ; i++) {
xB=0;
for(int j=column;j<column+8;j++) {
if(!squareB[yB][xB].equals(square[i][j])) {
countB++;
}
xB++;
}
yB++;
}
for(int i = row ;i<row+8 ; i++) {
xW=0;
for(int j=column; j<column+8; j++) {
if(!squareW[yW][xW].equals(square[i][j])) {
countW++;
}
xW++;
}
yW++;
}
return countB>=countW?countW:countB;
}
public static int getMin(ArrayList<Integer> list) {
int min = list.get(0);
for(int i=1; i<list.size();i++) {
if(list.get(i)<min) {
min = list.get(i);
}
}
return min;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String line=br.readLine();
StringTokenizer st = new StringTokenizer(line);
int N =Integer.parseInt(st.nextToken());
int M =Integer.parseInt(st.nextToken());
square = new String[N][M];
ArrayList<Integer> countList = new ArrayList<Integer>();
//지민이가 찾은 보드
for(int i=0; i<N;i++) {
String row = br.readLine();
for(int j=0;j<M;j++) {
square[i][j]=Character.toString(row.charAt(j));
}
}
//1. 8*8의 체스판의 시작점이 될 수 있는 보드의 좌표을 isRight의 매개변수로 넘긴다
//2. isRight 함수
// - 매개변수로 넘어온 보드의 시작점부터 마지막점까지
// - 각각 squareB(시작점이"B"인 8*8정사각형), squareW(시작점이"W"인 8*8 정사각형)과 비교해서
// - 다른 칸의 갯수가 최소인 것을 return
for(int row = 0; row <=N-8; row ++) {
for(int column = 0;column<=M-8 ;column++) {
int totalCount = isRight(row, column);
countList.add(totalCount);
}
}
bw.write(Integer.toString(getMin(countList)));
bw.close();
}
}
개선
isRight()의 함수 부분 개선
public static int isRight(int row, int column) {
int countB = 0;
int countW = 0;
for(int i=0; i<8 ; i++) {
for(int j=0; j<8; j++) {
String squareCell = square[row+i][column+j];
if(!squareCell.equals(squareB[i][j]))countB++;
if(!squareCell.equals(squareW[i][j])) countW++;
}
}
return countB>=countW?countW:countB;
}
좀 더 간단하게
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] line = br.readLine().trim().split(" ");
int N = Integer.parseInt(line[0]);
int M = Integer.parseInt(line[1]);
String[][] tempBoard = new String[N][M];
for(int r = 0; r<N ; r++){
tempBoard[r] = br.readLine().trim().split("");
}
MakeChess makeChess = new MakeChess(N,M,tempBoard);
makeChess.countColoring();
bw.write(String.valueOf(makeChess.getMinCount()));
bw.flush();
}
}
class MakeChess{
private final String[][] BLACK_CHESS ={
{"B","W","B","W","B","W","B","W"},
{"W","B","W","B","W","B","W","B"},
{"B","W","B","W","B","W","B","W"},
{"W","B","W","B","W","B","W","B"},
{"B","W","B","W","B","W","B","W"},
{"W","B","W","B","W","B","W","B"},
{"B","W","B","W","B","W","B","W"},
{"W","B","W","B","W","B","W","B"},
};
private final String[][] WHITE_CHESS ={
{"W","B","W","B","W","B","W","B"},
{"B","W","B","W","B","W","B","W"},
{"W","B","W","B","W","B","W","B"},
{"B","W","B","W","B","W","B","W"},
{"W","B","W","B","W","B","W","B"},
{"B","W","B","W","B","W","B","W"},
{"W","B","W","B","W","B","W","B"},
{"B","W","B","W","B","W","B","W"}
};
int N;
int M;
String[][] board;
ArrayList<Integer> minColoring;
MakeChess(int N, int M, String[][]tempBoard){
this.N = N;
this.M = M;
board = tempBoard;
minColoring = new ArrayList<>();
}
public void countColoring(){
for(int startRow = 0 ; startRow<=N-8; startRow++){
for(int startColumn = 0 ;startColumn<=M-8; startColumn++){
int count =compareChess(startRow,startColumn);
minColoring.add(count);
}
}
}
private int compareChess(int row, int column){
int countBlack =0;
int countWhite =0;
for(int r=row; r<row+8; r++){
for(int c=column; c<column+8 ; c++){
if(!board[r][c].equals(BLACK_CHESS[r-row][c-column])){
countBlack ++;
}
if(!board[r][c].equals(WHITE_CHESS[r-row][c-column])){
countWhite ++;
}
}
}
return Math.min(countBlack,countWhite);
}
public int getMinCount(){
Collections.sort(minColoring);
return minColoring.get(0);
}
}
반응형
'알고리즘 > 백준' 카테고리의 다른 글
| [백준 1326, 자바] 그룹단어 체커 -- 다시 (0) | 2020.03.12 |
|---|---|
| [백준 2789 자바] 블랙잭 (0) | 2020.03.08 |
| [백준 2231 자바] 분해합 (0) | 2020.03.03 |
| [백준 7568] 덩치 (0) | 2020.03.02 |
| [백준 1157] 단어공부 - 다시 (0) | 2020.03.01 |
Comments