21.08.17 기록

백준 알고리즘 1018 풀이

🎆나의 풀이(메모리 14.6MB, 시간 152ms로 통과)

-입력 받은 배열을 chessB와 chessW 배열과 모두 비교를 한다.
-요소의 일치하는 값(cntEqual)이 더 많으면 일치하지 않는 값을 바꾸고,
일치하지 않는 값(cntNotEqual)이 더 많으면 일치하는 값을 바꾸도록 한다.
-모든 경우의 수를 while문 안에서 돌면서, 가장 최소 움직임을 min에 저장하고 min 값을 최종적으로 출력한다.

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.StringTokenizer;

  public class B1018 {
      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.parseInt(st.nextToken());
          int M = Integer.parseInt(st.nextToken());

          //모든 문자를 CHAR 배열로 저장
          String[] strArr = new String[N];
          char[][] inputs = new char[M][N];
          for(int j = 0; j < N; j++) {
              strArr[j] = br.readLine();
              for(int i = 0; i < M; i++) {
                  inputs[i][j] = strArr[j].charAt(i);
              }
          }
          final char[][] chessB = { {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'}
                                  , {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'}
                                  , {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'}
                                  , {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'}
                                  , {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'}
                                  , {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'}
                                  , {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'}
                                  , {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'} };

          final char[][] chessW = { {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'}
                                  , {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'}
                                  , {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'}
                                  , {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'}
                                  , {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'}
                                  , {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'}
                                  , {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'}
                                  , {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'} };

          //첫번째 요소
          int x = 0;
          int y = 0;

          int min = Integer.MAX_VALUE;
          while(true) {
              int cntEqualB = 0;
              int cntNotEqualB = 0;

              int cntEqualW = 0;
              int cntNotEqualW = 0;
              for(int j = y; j < (y+8); j++) {
                  for(int i = x; i < (x+8); i++) {
                      if(inputs[i][j] == chessB[i-x][j-y]) { cntEqualB++; }
                      else { cntNotEqualB++; }
                      if(inputs[i][j] == chessW[i-x][j-y]) { cntEqualW++; }
                      else { cntNotEqualW++; }
                  }
              }

              int compare = 0;
              if(cntEqualB > cntNotEqualB) { compare = cntNotEqualB; }
              else { compare = cntEqualB; }

              if(cntEqualW > cntNotEqualW && cntEqualW < compare ) { compare = cntEqualW; }
              else {
                  if(cntNotEqualW < compare) { compare = cntNotEqualW; }
              }

              if(compare < min) { min = compare; }

              x++;
              if((x+8) > M) {
                  x = 0;
                  y++;
              }

              if((y+8) > N) { break; }
          }
          System.out.println(min);
      }
  }

🎆해설(메모리 14.2MB, 시간 140ms로 통과)

-해설은 boolean 배열을 사용하여 풀이했다.

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.StringTokenizer;

  public class B1018 {
      public static boolean[][] chess;
      public static int min = 64;
      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.parseInt(st.nextToken());
          int M = Integer.parseInt(st.nextToken());

          chess = new boolean[N][M];

          //1. 입력값이 W이면 true 값을, B이면 false 값을 chess 배열에 저장한다.
          String str = "";
          for(int i = 0; i < N; i++) {
              str = br.readLine();
              for(int j = 0; j < M; j++) {
                  if(str.charAt(j) == 'W') { chess[i][j] = true; }
                  else { chess[i][j] = false; }
              }
          }

          //2. 전체 범위에서 check 함수를 수행 후 최솟값을 찾는다.
          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++) {
                  check(i,j);
              }
          }
          System.out.println(min);
      }

      public static void check(int x, int y) {
          int endX = (x+8);
          int endY = (y+8);
          int cnt = 0;

          //2-1. 8x8 체스의 첫번째 요소 값을 tf로 저장한다.
          boolean tf = chess[x][y];

          //2-2. not 연산자로 tf에 변화를 주어 값을 비교한다.
          for(int i = x; i < endX; i++) {
              for(int j = y; j < endY; j++) {
                  if(chess[i][j] != tf) { cnt++; }
                  tf = (!tf);
              }
              tf = !tf;
          }

          //2-3. 새로 색칠할 개수 vs 반대 색으로 색칠된 개수
          cnt = Math.min(cnt, (64-cnt));  //더 작은 값을 저장한다.

          //2-4. cnt가 min값보다 더 작을 때 min 값을 새로 저장한다.
          min = Math.min(min, cnt);
      }
  }