[브루트포스] 백준 - 체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

 

-문제해설

자바의 첫 번째 소스코드는 미리 올바른 체스판 배열을 만든 다음 입력배열과 비교하는 코드이다.
문제에서는 최소한 가로세로 8이상이라고 했는데 잠시 예시를 위해 4*4을 입력받는다고 해보자.

4*4의 올바른 체스판은 아래와 같다.

-W로 시작할 경우
WBWB
BWBW
WBWB
BWBW

-B로 시작할 경우
BWBW
WBWB
BWBW
WBWB

이런 올바른 배열을 두 개 다 만들 필요없이 하나만 만들고 16에서 빼주면 된다.

만약 4*4에서 입력배열이 아래와 같다고 해보자.

WBBW
BWBW
BBBB
BWBW

여기서 그냥 W나 B로 시작하는 올바른 배열 하나만 만든다. W로 시작하는 올바른 배열을 만들면 아래와 같다.

WBWB
BWBW
WBWB
BWBW

올바른 배열과 비교했을 때 정답은 3이 되어야 한다. B로 시작하는 배열의 경우 16-3=15가 된다.

따라서 3과 15 중에 최소값을 출력하면 정답이 된다.

문제에서는 8*8의 체스판이므로 64에서 빼주면 된다.

 

자바의 두 번째 소스코드는 위에처럼 올바른 배열을 만드는게 아니라 그냥 임의의 문자를 계속 바꿔가면서 입력 배열과 비교하는 것이다.

예를 들어 c라는 문자를 처음에 W라고 지정해놓고 현재 입력배열값과 다르면 1을 더하고 아니면 c문자를 B로 바꿔준다.

대충 이런식이다.

if( c != arr[i][j] ) sum++;

c = 'B';

여기서도 마찬가지로 마지막에 sum과 64-sum을 비교해서 더 작은 값을 출력하도록 한다.

코드 성능은 두 번째 소스코드가 더 좋아서 파이썬도 두 번째 방법으로 풀었다.

 

 

-자바(미리 올바른 체스판 배열을 만들고 비교하기)

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.StringTokenizer;

public class BJ1018 {
	private static BufferedWriter bw = 
			new BufferedWriter( new OutputStreamWriter(System.out));
	private static int n, m, x_start, y_start, x_end, y_end, min, sum, sum1;
	private static char[][] arr, ans1;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer( br.readLine() );
		n = Integer.parseInt( st.nextToken() );
		m = Integer.parseInt( st.nextToken() );
		String tmp = "";
		
		arr = new char[n+1][m+1];
		ans1 = new char[n+1][m+1];
		
		for( int i=1; i<=n; i++ ) {
			tmp = "0"+br.readLine();
			for( int j=1; j<=m; j++ ) {
				arr[i][j] = tmp.charAt(j);
				if( i==1 && j==1 ) {
					ans1[i][j] = 'B';
				} else if( i!=1 && j==1 ) {
					ans1[i][j] = m%2==0 ? ans1[i-1][m] : ans1[i-1][m-1];
				} else {
					ans1[i][j] = ans1[i][j-1] == 'W' ? 'B':'W';
				}
			}
		}
		
		sum = Integer.MAX_VALUE;
		min = Integer.MAX_VALUE;
		for( int i=1; i<=n-7; i++ ) {
			y_start = i;
			y_end = i+7;
			
			for( int j=1; j<=m-7; j++ ) {
				x_start = j;
				x_end = j+7;
				sum1 = 0;
				
				for( int k=y_start; k<=y_end; k++ ) {
					for( int z=x_start; z<=x_end; z++ ) {
						if( arr[k][z] == ans1[k][z] ) sum1++;					
					}
				}
				sum = Math.min( sum1, 64-sum1 );
				min = Math.min( sum, min );
			}
		}
		
		bw.write( min + "\n" );
		bw.flush();
		bw.close();
		br.close();
	}
}

 

-자바(특정문자의 값을 계속 바꿔주면서 배열값이랑 비교하기)

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.StringTokenizer;

public class BJ1018 {
	private static BufferedWriter bw = 
			new BufferedWriter( new OutputStreamWriter(System.out));
	private static int n, m, min, sum, sum1;
	private static char[][] arr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer( br.readLine() );
		n = Integer.parseInt( st.nextToken() );
		m = Integer.parseInt( st.nextToken() );
		String tmp = "";
		
		arr = new char[n][m];
		
		for( int i=0; i<n; i++ ) {
			tmp = br.readLine();
			for( int j=0; j<m; j++ ) arr[i][j] = tmp.charAt(j);
		}
		
		sum = Integer.MAX_VALUE;
		min = Integer.MAX_VALUE;
		for( int i=0; i<n-7; i++ ) {
			for( int j=0; j<m-7; j++ ) {
				char c = arr[i][j];
				sum1 = 0;
							
				for( int k=i; k<i+8; k++ ) {
					for( int z=j; z<j+8; z++ ) {
						if( arr[k][z] != c ) sum1++;
						
						if( z==j+7 ) continue;
						else if( c=='W' ) c='B';
						else if( c=='B' ) c='W';
					}
				}
				sum = Math.min( sum1, 64-sum1 );
				min = Math.min( sum, min );
			}
		}
		
		bw.write( min + "\n" );
		bw.flush();
		bw.close();
		br.close();
	}
}

 

-파이썬

n, m = map(int, input().split())
arr = []
a = 999

for _ in range( n ):
    arr.append( input() )

for i in range( n-7 ):
    for j in range( m-7 ):
        c = arr[i][j]
        s = 0
        for k in range( i, i+8 ):
            for z in range( j, j+8 ):
                if arr[k][z]!=c: s += 1

                if z==j+7: continue
                elif c=='W': c = 'B'
                elif c=='B': c = 'W'

        s = min( s, 64-s )
        a = min( s, a )
        
print( a )