(JAVA) 백준 1018번 : 체스판 다시 칠하기

https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

 

이건 좀

브루트 포스에 가까운

시뮬레이션 문제였습니다..

 

 

정공법으로

for문으로 탐색해도 메모리 크게 차지하지 않더군요.. 속도도 높지 않고.

 

 

 

 

메커니즘을 포스팅할거지만

 

다른 사람들 풀이 방법을 보니

 

꼭 제가 푸는 방법이 정답이 아닐 수 있어

 

 

제가 어떤식으로 이 문제를 풀었는지

 

핵심만 적겠습니다!

 

 

저는 우선

 

크게

 

1) W로 시작

2) B로 시작

(인덱스가 0 부터 n - 1 까지라고 가정했을 때 0, 0에 해당하는 값)

두 갈래로 나눠서

 

2차원 배열 boolean 2개를 만들었습니다.

*** 굳이 배열 만들지 않고 바로 for문 돌려서 비교해도 될 것 같군요..

 

 

해당 인덱스의 값이 'W' 인 경우

     짝수행 -> 짝수열 : B로 시작할 경우 B가 들어와야 하기 때문에 다시 칠해야 함. 따라서, 2) 배열의 같은 인덱스의 원소 값을 true로 변경.

     짝수행 -> 홀수열 : W로 시작할 경우 B가 들어와야 하기 때문에 다시 칠해야 함. 따라서, 1) 배열의 같은 인덱스의 원소 값을 true로 변경.

     홀수행 -> 짝수열 : W로 시작할 경우 B가 들어와야 하기 때문에 다시 칠해야 함. 따라서, 1) 배열의 같은 인덱스의 원소 값을 true로 변경.

     홀수행 -> 홀수열 : B로 시작할 경우 B가 들어와야 하기 때문에 다시 칠해야 함. 따라서, 2) 배열의 같은 인덱스의 원소 값을 true로 변경.

 

 

이런 공식으로 해당 인덱스의 값이 'B' 인 경우에도 처리를 해줍니다.

 

 

 

마지막으로, 8 x 8 배열 고정으로 다시 칠하는 최소 경우를 구해야 하기 때문에

 

8 x 8 배열 내 true인 값이 있으면 counting을 진행하고, 

 

이중 가장 최소인 값을 출력하면 끝!

*** for문 진행 시 y = 0; y <= 전체 y길이 - 8; y++ 2중 for문(x도 똑같이) 방식으로 진행해야 인덱스 초과 없이 전부 탐색 가능합니다.

 

 

 

 

 

감사합니다.

 

소스코드

---

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	// 체스판 다시 칠하기
	// 시뮬레이션
	public class p1018 {
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	int n = Integer.valueOf(st.nextToken());
	int m = Integer.valueOf(st.nextToken());
	boolean[][] startB = new boolean[n][m]; // B로 시작할 때 다시 칠해야 하는 것
	boolean[][] startW = new boolean[n][m]; // W로 시작할 때 다시 칠해야 하는 것
	char[][] map = new char[n][m];
	for(int i = 0; i < n; i++) {
	char[] line = br.readLine().toCharArray();
	map[i] = line;
	}
	// 다시 칠해야 할 부분 정리
	for(int y = 0; y < n; y++) {
	for(int x = 0; x < m; x++) {
	// 행 조건
	// 짝수 행
	if(y % 2 == 0) {
	if(map[y][x] == 'B') {
	if(x % 2 == 0) { // 홀수 열에서는 W로 시작할 때 B가 오면 다시 칠해야 한다.
	startW[y][x] = true;
	}
	else { // 짝수 열에서는 B로 시작할 때 W가 오면 다시 칠해야 한다.
	startB[y][x] = true;
	}
	}
	else { // 'W'인 경우
	if(x % 2 == 0) {
	startB[y][x] = true;
	}
	else { // 짝수 열에서는 W로 시작할 때 W가 오면 안된다.
	startW[y][x] = true;
	}
	}
	}
	// 홀수 행
	else {
	if(map[y][x] == 'B') {
	if(x % 2 == 0) { // 홀수 열에서는 B로 시작할 때 B가 오면 다시 칠해야 한다.
	startB[y][x] = true;
	}
	else { // 짝수 열에서는 W로 시작할 때 B가 오면 다시 칠해야 한다.
	startW[y][x] = true;
	}
	}
	else { // 'W'인 경우
	if(x % 2 == 0) {
	startW[y][x] = true;
	}
	else { // 짝수 열에서는 B로 시작할 때 W가 오면 안된다.
	startB[y][x] = true;
	}
	}
	}
	}
	}
	int maxW = 0;
	int maxB = 0;
	int min = Integer.MAX_VALUE;
	for(int y = 0; y <= n - 8; y++) {
	for(int x = 0; x <= m - 8; x++) {
	int cntW = 0;
	int cntB = 0;
	for(int t = y; t < y + 8; t++) {
	for(int k = x; k < x + 8; k++) {
	if(startW[t][k]) {
	cntW++;
	}
	if(startB[t][k]) {
	cntB++;
	}
	}
	}
	min = Math.min(min, Math.min(cntW, cntB));
	}
	}
	System.out.println(min);
	}
	}

view raw p1018.java hosted with ❤ by GitHub