반응형
📝문제
1018번: 체스판 다시 칠하기
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
www.acmicpc.net
💡Problem
- 8 x 8 체스판을 자르는 문제로 흰색과 검은색이 번갈아 색칠되어야 한다.
- 자른 8 x 8 체스 안에서 번갈아 색칠되지 않은 공간의 개수를 찾는다.
- 체스판에서 8 x 8 체스판으로 자르는 경우는 여러 경우가 나올 수 있다.
- 자른 여러 체스판 중에서 가시 칠해야 하는 정사각형의 최소 개수를 구하면 된다.
🔑Solution
💻Code
import java.util.Scanner;
public class Main {
public static boolean[][] map;
public static int min = 64;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
map = new boolean[N][M];
/*
Scanner 의 경우 공백자로 구분하다가 개행으로 입력되면
스트림에 개행이 남아있어서 의도와 달리 첫 번째 String 입력은 개행이
저장된다. 그렇기 때문에 nextLine() 을 통해 문자열
입력 전의 int와 String 입력 사이의 개행을 없애주도록 한다.
*/
sc.nextLine();
for (int i = 0; i < N; i++) {
String str = sc.nextLine().trim();
for (int j = 0; j < M; j++) {
if (str.charAt(j) == 'W') {
map[i][j] = true;
} else {
map[i][j] = false;
}
}
}
int N_row = N - 7;
int M_col = M - 7;
for (int i = 0; i < N_row; i++) {
for (int j = 0; j < M_col; j++) {
find(i, j);
}
}
System.out.println(min);
}
public static void find(int x, int y) {
int end_x = x + 8;
int end_y = y + 8;
int count = 0;
boolean FirstBoolean = map[x][y];
for (int i = x; i < end_x; i++) {
for (int j = y; j < end_y; j++) {
if (map[i][j] != FirstBoolean) {
count++;
}
/*
다음 칸은 색이 바뀌므로 true라면 false로,
false 라면 true 로 값을 변경한다.
*/
FirstBoolean = (!FirstBoolean);
}
FirstBoolean = !FirstBoolean;
}
/*
첫 번째 칸을 기준으로 할 때의 색칠 할 개수(count)와
첫 번째 칸의 색의 반대되는 색을 기준으로 할 때의
색칠 할 개수(64 - count) 중 최솟값을 count 에 저장
*/
count = Math.min(count, 64 - count);
min = Math.min(min, count);
}
}
'알고리즘 > 백준(JAVA)' 카테고리의 다른 글
[백준] 15652번: N과 M(4) [JAVA-자바] (0) | 2021.01.19 |
---|---|
[백준] 1436번: 영화감독 숌 [JAVA-자바] (0) | 2021.01.19 |
[백준] 2748번: 피보나치 수 2 [JAVA-자바] (0) | 2021.01.12 |
[백준] 1003번: 피보나치 함수 [JAVA-자바] (0) | 2021.01.12 |
[백준] 15650번: N과 M(2) [JAVA-자바] (0) | 2021.01.08 |
댓글