알고리즘 풀이(JAVA) - 백준 알고리즘_1018(브루트포스-체스판 다시 칠하기)

By on September 17, 2019

브루트포스(brute-force)

  • 브루트포스란?
    brute는 “짐승같은, 난폭한”이라는 뜻이고, brute-force는 “난폭한 힘, 폭력”이라는 뜻이다. 암호학 용어로는 brute-force attack 또는 exhaustive key search, 우리말로는 노가다 또는 무차별 대입 공격이라 부른다. 주로 암호학에서도 쓰이는 방법이긴 하지만, 굳이 암호학만의 문제는 아니고 다른 알고리즘 분야에서도 사용되고 있다. 간단하게 말하자면 노가다와 다굴을 논리적이고 과학적으로 하는 방식.

  • 특징
    조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 문제를 푸는 것인데, 얼핏 무식하다고 생각할 수도 있겠지만 성공한다는 가정 하에 항상 정확도 100%를 보장한다는 점에서, 자원만 충분하면 가장 무서운 방법이다. 이론적으로 가능한 모든 경우의 수를 다 검색해 보는 것이라 정확도 100%가 항상 보장되니, 암호학에서는 가장 확실한 방법으로 통용되고 있다. 무엇보다도 암호 확인 작업이라는 것이 손으로 입력한 문자열의 동일 여부를 확인하는 것이기 때문에, 가능한 경우를 하나씩 대입하다 보면 언젠가는 암호를 찾을 수 있게 되는 식이다. 다만 정말로 그냥 무식하게 때려박는 건 아니고, 숫자만 섞어서 대입해보기 한번, 로마자만 섞어서 대입해보기 한번 이런식으로 하다가 안되면 나머지를 순차적으로 하는 식으로 특정 규칙에 따라 우선순위를 두고 하기도 한다.

문제

문제 링크 : https://www.acmicpc.net/problem/1018

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 MN 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다.
지민이는 이 보드를 잘라서 88 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다.
따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 88 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다.
당연히 88 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

풀이

이 문제를 풀때 2번이나 틀렸다. 아래는 왜 실패 했는지 케이스이다.

실패1) 8 * 8 크기의 배열을 만들어서 처음부터 시작해서 양옆을 비교해서 색을 바꾸려고 했다. 이경우 아래 반문으로 인해 깨닳음. 8 8
BBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

위 경우 0,0 번째 B 하나만 바꾸면 되는데 양옆을 비교해서 바꾸다보니 첫번째를 기준으로 다바꿔버려서 실패.

실패2) 단순히 체스판이라고 생각했다. 고정된 색깔과 고정된 사이즈 하지만 문제를 제대로 안읽었다.

체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

풀이)

  • 입력 받은 M*N 사이즈의 배열을 만든다.
    • String[][] inputReader(BufferedReader reader, int M, int N)
  • 배열의 전체사이즈를 반복 하면서 8 * 8 사이즈의 미완성된 체스판을 만든다.
    • makeChess(String[][] arr, int x, int y)
  • 미완성된 체스판을 한칸을 읽어 완성된 체스판과 비교 하여 몇 번이나 색칠을 해야 할지 카운터를 센다.
    • paintBoard(String[][] board)
  • 가장 작은 카운터를 반환한다.

소스

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

public class Baekjoon_1018 {
	
	static final String[][] caseA = {
			{"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"}
	};
	
	static final String[][] caseB = {
			{"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"}
	};
	
	public static void main(String[] args) {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		try {
			String[] boardSize = reader.readLine().split(" ");
			String[][] inputBoard = inputReader(reader, Integer.parseInt(boardSize[0]), Integer.parseInt(boardSize[1]));
			
			int tmp = 0;
			int minPaint = 64;
			for(int i = 0; i <= inputBoard.length - 8; i++) {
				for(int j = 0; j <= inputBoard[i].length - 8; j++) {
					tmp = makeChess(inputBoard, i, j);
					minPaint = Math.min(minPaint, tmp);
				}
			}
			System.out.println(minPaint);
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
    
    //입력을 받는다.
	private static String[][] inputReader(BufferedReader reader, int M, int N) throws IOException {
		String[][] arr = new String[M][N];
		for(int i = 0; i < arr.length; i++) {
			String[] board = reader.readLine().split("");
			for (int j = 0; j < board.length; j++) {
				arr[i][j] = board[j];
			}
		}
		return arr;
	}
    
    //보드를 만든다 8 * 8
	private static int makeChess(String[][] arr, int x, int y) {
		String[][] board = new String[8][8];
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				board[i][j] = arr[i + x][j + y];
			}
		}
		return paintBoard(board);
	}

    //틀린부분을 찾아서 카운터 한다.
	private static int paintBoard(String[][] board) {
		int caseACnt = 0;
		int caseBCnt = 0;
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				if(caseA[i][j].equals(board[i][j])) {
					caseACnt++;
				}
				if(caseB[i][j].equals(board[i][j])) {
					caseBCnt++;
				}
			}
		}
		return Math.min(caseACnt, caseBCnt);
	}
	
    //출력
	private static void print(String[][] arr) {
		for (String[] strings : arr) {
			for (String s : strings) {
				System.out.print(s);
			}
			System.out.println();
		}
	}
}

Back to blog