백준 1018 체스판 다시 칠하기 ] 브루트포스 / 배열 JAVA

브루트포스 알고리즘은 무식하게 모든 경우의 수를 다 살펴보는 알고리즘이다.
예를들어 1~1000중에 555가 답이라고 했을때
1이 답인가?
2가 답인가?
3이 답인가?
...

554가 답인가?
555가 답인가?

이런식으로 하나하나 다 살펴보는 것으로 완전탐색이라고 하기도 한다.

소스코드

import java.util.*;
public class Main {
    //결과는 두 가지 케이스로 이루어져있다.
    static String[] Wresult = {"WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW"};
    static String[] Bresult = {"BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB"};


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        //크기입력받습니다.
        int N = sc.nextInt();
        int M = sc.nextInt(); String whatthe__ = sc.nextLine();

        //NM체스판 입력받습니다.
        String[] NM = new String [N];
        for(int i = 0; i < N ; i ++) {
            NM[i] = sc.nextLine();                    
        }

        //결과 세겠습니다.
        int result = 2500;//최댓값

        for(int i = 0 ; i+7 < N ; i++)
            for(int j = 0 ; j+7 < M ; j++) 
                result = min(result,checkW(NM,i,j),checkB(NM,i,j));


        System.out.println(result);

    }    

    static int checkW(String[] NM, int i, int j) {
        int result = 0;

        for(int a = i; a < i+8; a++)
            for(int b = j; b < j+8 ; b++)
                if(NM[a].charAt(b) == Bresult[a-i].charAt(b-j)) result++;

        return result;    
    }


    static int checkB(String[] NM, int i, int j ) {
        int result = 0;

        for(int a = i; a < i+8; a++)
            for(int b = j; b < j+8 ; b++ )
                if(NM[a].charAt(b) == Wresult[a-i].charAt(b-j)) result++;

        return result;
    }

    static int min(int a, int b, int c) {
        return (a<b?(a<c?a:c):(b<c?b:c));
    }
}

크기 및 체스판 입력 받고,
(크기받을때 nextLine알아서 하나 더 먹길래 추가해주었다.)

최대 N, M은 각 50씩이므로 나올 수 있는 result 최댓값은 2500이다.
여기서 min(최소로 드는 값)을 구하면 되는 것이므로

WBWBWB로 하는 결과와
BWBWBW로 하는 결과 중 최소로 드는 값을 출력하면 된다.

이미 8x8크기의 결과값을 지정해두고 결과가 되기 위해서는 몇 개를 수정해야되냐를 확인하는 문제였다.

여기서 문제는, 입력받은 값이 8x8크기면 8x8크기인 답과 바로 비교를 해주면 됐지만,
입력받은 체스판이 8이상의 NxM이면 8x8과 1:1로 직접 비교를 할 수 없는데 있다.

그래서 입력받은 체스판을 8x8크기로 쪼개서 checkW() checkB()함수에서 1:1로 비교해주는 방식을 택했다.

(그림은 i = 8, 9, 10인 경우를 나타냈다. j = 8, 9, 10, 11, 12, 13인 경우도 for문으로 돌려주므로, 총 15번 비교를 한 결과(result)중 최솟값을 택해 출력한다.)

브루트포스인이유는 8x8로 쪼개서 나올 수 있는 모든 경우를 checkW와 checkB으로 대입시켜주었기 때문이다.

참고 https://jaimemin.tistory.com/667

---

참고로 최소가 되는 행의 집합을 하려고 하면 열의 갯수가 항상 8이 아니기 때문에 결국 행과 열의 모든 경우의 수를 따지는 방법밖엔 없다.

---

두 번째로 다시 푼 코드

import java.util.Arrays;
import java.util.Scanner;



public class Main {

     static String[] Wresult = {"WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW"};
     static String[] Bresult = {"BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB"};

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        int row = sc.nextInt();
        int col = sc.nextInt();
        String empty = sc.nextLine();
        String[] chess = new String[row];

        int result = 2500;

        for(int i = 0 ; i < row; i ++)
            chess[i]= sc.nextLine();

        for(int i = 0 ; i < row-7; i ++)
            for(int j = 0 ; j < col-7; j++)
                result =  minNum(result, checkW(chess,i, j), checkB(chess,i,j));

        System.out.println(result);

    }

    public static int checkW(String[] chess, int a, int b) {
        int result = 0;
        for(int i = a ; i < a + 8 ; i ++)
            for(int j = b ; j < b + 8; j++){
                if(chess[i].charAt(j) == Wresult[i-a].charAt(j-b)) result++;
            }
        return result; 
    }
    public static int checkB(String[] chess, int a, int b) {
        int result = 0;
        for(int i = a ; i < a + 8 ; i ++)
            for(int j = b ; j < b + 8; j++){
                if(chess[i].charAt(j) == Bresult[i-a].charAt(j-b)) result++;
            }
        return result; 
    }

   public static int minNum(int a, int b, int c) {

       int[] three = new int[3];
       three[0] = a; three[1] = b;three[2] = c;
       Arrays.sort(three);
       return three[0];

   }
}

---

연습

1. 8*8의 체스판이 주어졌을 때

import java.util.Scanner;

public class Main {

//1. 체스판 answer 입력
static String[] Wresult = {"WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW"};
static String[] Bresult = {"BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB"};

public static void main(String[] args) {

    //2. 체스판 입력받기
    Scanner sc = new Scanner(System.in);
    int row = sc.nextInt();
    int col = sc.nextInt();
    String empty = sc.nextLine();//공백문자처리
    String[] chess = new String[row];

    int result = 2500;

    for(int i = 0 ; i < row; i ++)
        chess[i]= sc.nextLine();

    // 2.1 8*8 체스판 비교하기
    int wCount = 0;
    int bCount = 0;

    for(int i = 0; i < 8; i++) {
        for(int j = 0; j < 8; j++) {
            if(Wresult[i].charAt(j) == chess[i].charAt(j))
                wCount++;
            if(Bresult[i].charAt(j) == chess[i].charAt(j))
                bCount++;
        }
    }

    //2.2 result 반환
// System.out.println(result +" "+ wCount +" "+ bCount );  
System.out.println(result > wCount? (wCount > bCount? bCount:wCount ):result );

}

}

2. 8*8 보다 큰 체스판이 주어졌을 때 (맨 위의 답)