[백준] no1018 체스판 다시 칠하기

방법 1

: 재귀를 이용한 구하기

: hyoreal51님의 하드캐리!! 출처 : https://hyospital.tistory.com/47

 

1. 보드를 입력받아 완성한다

2. 보드에서 8*8로 될 수 있는 시작점을 반복문을 통해 지정한다.

3. 2에서 지정한 시작점으로 부터 8*8만큼 순회한다.

4. 만약 현재지점에서 오른쪽을 확인하여 같은 색(B or W)이면 다른색으로 칠해준다

5. 만약 현재지점에서 아래쪽을 확인하여 같은 색(B or W)이면 다른색으로 칠해준다.

6. 만약 모든 지점을 다 칠하면(현재 지점의 행렬값이 8*8일때) count를 반환한다.

7. 만약 중간에 min보다 count가 더 크다면 멈추고, 다음 최초지점에서 8*8을 순회한다.

8. 결과적으로 제일 작은 값이 된 min을 출력한다.

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 행렬을 받아옴
        String[][] data = new String[N][M];
        for (int i = 0; i < N; i++) {
            String temp = br.readLine();
            for (int j = 0; j < M; j++) {
                data[i][j] = String.valueOf(temp.charAt(j));
            }
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < N - 7; i++) {
            for (int j = 0; j < M - 7; j++) {
                int temp = recur(0, data,i, j, 0, 0);
                if (min > temp) min = temp;
            }
        }

        bw.write(""+min+"\n");
        bw.close();
    }


    private static int recur(int count, String[][] data, int low, int cul, int j, int i) {
        String[][] stanBoard = {
                {"W", "B", "W", "B", "W", "B", "W" ,"B"},
                {"B", "W", "B", "W", "B", "W", "B", "W"}
        };

        // 최종탈출
        if (j == 8) {
            return Math.min(count, 64 - count);
        }

        // count영역
        if (i == 7 && j == 7) {
            if (!data[low+i][cul+j].equals(stanBoard[(low+i) % 2][j])) {
                count = recur(count + 1, data, low, cul, j+1, i);
            }
        } else if (i != 7 && j == 7) {
            if (!data[low+i][cul+j].equals(stanBoard[(low+i) % 2][j])) {
                count = recur(count+1, data, low, cul, 0, i+1);
            }
            else count = recur(count, data, low, cul, 0, i+1);
        } else if (i == 7 && j != 7) {
            if (!data[low+i][cul+j].equals(stanBoard[(low+i) % 2][j])) {
                count = recur(count+1, data, low, cul, j+1, i);
            }
            else count = recur(count, data, low, cul, j+1, i);
        } else if (i != 7 && j != 7) {
            if (!data[low+i][cul+j].equals(stanBoard[(low+i) % 2][j])) {
                count = recur(count+1, data, low, cul, j+1, i);
            }
            else count = recur(count, data, low, cul, j+1, i);
        }

        return count;
    }
}

---

시도 2

: 되긴함. for문 쌩으로 쌔리박음

mport java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        if(N<8 || M<8) {
            bw.write(""+0+"\n");
            bw.close();
        }

        List<String> Atype = new ArrayList<>();
        List<String> Btype = new ArrayList<>();
        for(int i=1; i<=8 ; i++) {
            String BW = "BWBWBWBW";
            String WB = "WBWBWBWB";
            if(i%2==1) {
                Atype.add(BW);
                Btype.add(WB);
            } else if (i%2==0) {
                Atype.add(WB);
                Btype.add(BW);
            }
        }

        String[][] data = new String[N][M];
        for (int i = 0; i < N; i++) {
            String temp = br.readLine();
            for (int j = 0; j < M; j++) {
                data[i][j] = String.valueOf(temp.charAt(j));
            }
        }

        int min = 64;
        for(int i=0; i<=N-8 ; i++) {
            for(int j=0 ; j<=M-8 ; j++) {
                min = compare(Atype, Btype, data, i, j, min);
            }
        }

        bw.write(""+min+"\n");
        bw.close();
    }

    private static int compare (List<String> Atype, List<String> Btype, String[][] data, int low, int col, int min) {
        int countA = 0;
        int countB = 0;
        int result = 0;
        
        for(int i=low; i<low+8; i++){
            for(int j=col; j<col+8; j++) {
                if(!data[i][j].equals(String.valueOf(Atype.get(i-low).charAt(j-col)))) countA++;
            }
        }

        for(int i=low; i<low+8; i++){
            for(int j=col; j<col+8; j++) {
                if(!data[i][j].equals(String.valueOf(Btype.get(i-low).charAt(j-col)))) countB++;
            }
        }

        if(countA>=min && countB>=min) result = min;
        else if(countA<countB) result = countA;
        else if(countB<=countA) result = countB;
        
        return result;
    }
}