Notice
Recent Posts
Link
- Today
- Total
hye-log
[백준]1018번 체스판 칠하기(JAVA) 본문
0. 문제 링크
https://www.acmicpc.net/problem/1018
1. 문제 설명
1) M*N 체스판을 잘라 각 칸을 검은색이나 흰색으로 번갈아 있는 8*8 체스판을 만들려고 함
2) 다시 칠해야 하는 정사각형 개수의 최소값 구하기
2. 입출력
// input
8 8 // M N
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
// output
1
3. 코드
import java.io.*;
import java.util.*;
public class b1018 {
private static boolean[][] map;
private static int ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken()); // 가로
int N = Integer.parseInt(st.nextToken()); // 세로
map = new boolean[M][N]; // 체스판
for (int i = 0; i < M; i++) {
String s = br.readLine();
for (int j = 0; j < N; j++) {
if(s.charAt(j) == 'W') {
map[i][j] = true;
} else map[i][j] = false;
}
}
ans = Integer.MAX_VALUE;
int temp = 0; // 다시 칠해야 하는 정사각형의 개수
for (int i = 0; i <= M-8; i++) { // 8*8 체스판으로 잘라서 생각
for (int j = 0; j <= N-8; j++) {
// 기준점이 true
temp = 0;
if(map[i][j] != true) temp++; // 기준점이 true가 아니면 칠하기
find(i, j, true, temp); // 8*8 체스판 확인
// 기준점이 false
temp = 0;
if(map[i][j] != false) temp++; // 기준점이 false가 아니면 칠하기
find(i, j, false, temp); // 8*8 체스판 확인
}
}
System.out.println(ans); // 출력
}
private static void find(int i, int j, boolean check, int temp) {
for (int r = i; r < i+8; r++) {
for (int c = j; c < j+8; c++) {
if(r == i && c == j) continue; // 첫 칸은 패스
else if(c == j) { // 다음 줄의 첫 칸
if(check != map[r][c]) {
temp++;
}
}
else if(check == map[r][c]) {
temp++; // 정사각형 칠하기
check = !map[r][c]; // 바꾸기
}
else {
check = map[r][c];
}
}
}
ans = Math.min(ans, temp); // 최소값 찾기
}
}
실행 결과
4. 회고
1) 체스판에는 W(hite), B(lack) 두 가지 경우만 존재하므로 char보다는 boolean으로 만듦
- W가 아닐 때는 B, B가 아닐 때는 W로 상태를 쉽게 바꿀 수 있음
2) 8*8 체스판의 (0,0) 값을 기준으로 W, B 두 가지 경우를 모두 판단해야 함
3) (0,0) 첫 칸, (r, 0) 다른 줄의 첫 칸, 나머지 칸의 경우로 나누어서 다시 칠해야 하는지 판단
5. Github
728x90
'CodingTest > Baekjoon' 카테고리의 다른 글
[백준]1920번 수 찾기(JAVA) (0) | 2023.08.18 |
---|---|
[백준]1676번 팩토리얼 0의 개수(JAVA) (0) | 2023.08.18 |
[백준]10989번 수 정렬하기 3(JAVA) (0) | 2023.08.18 |
[백준]10828번 스택(JAVA) + 스택 직접 구현 (0) | 2023.08.18 |
[백준]1436번 영화감독 숌(JAVA) (0) | 2023.08.15 |
Comments