1. 문제 해석
흰색, 검은색의 정사각형들로 구성된 MxN 크기의 보드를 8x8 크기로 잘라서 체스판으로 활용하려고 합니다.
색 구별은 임의로 되어 있어서 보드를 자르고 난 뒤에는 체스판에 맞게 색을 덧칠한다고 합니다.
이때 색을 덧칠하는 횟수가 최소가 되는 보드 위치를 찾는 것이 요구사항입니다.
해당 문제에서 중요한 부분은 설명란의 2번째 구문입니다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, (중략) 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. (중략) 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
이는 맨 왼쪽 위칸이 흰색인 경우(이하 'case_white')와 검은색인 경우(이하 'case_black') 모두 고려해서 알고리즘을 작성해야 함을 의미합니다.
이유는 문제의 예제를 통해서 설명하겠습니다.
1 2 3 4 ... 16 17 18 19 20 21 22 23
1 B B B B ... B B B B B B B B
2 B B B B ... B B B B B B B B
3 B B B B ... B B B B B B B B
4 B B B B ... B B B B B B B B
5 B B B B ... B B B B B B B B
6 B B B B ... B B B B B B B B
7 B B B B ... B B B B B B B B
8 B B B B ... B B B B B B B B
9 B B B B ... B B B B B B B W
(B는 black, W는 white)
위의 보드는 (9, 23)만 W로 칠해져 있습니다.
(9, 23)을 제외한 구역을 자르면 모든 사각형이 B이기 때문에 총 32번의 W를 덧칠해야 합니다.
따라서 (2, 16)부터 (9, 23)까지의 구역을 잘라야 1번의 횟수를 더 줄이게 됩니다.
잘린 보드를 case_black으로 간주하면 각 줄마다 4개의 W가 덧칠될 것이고, 마지막 9행은 W로 시작해서 B로 끝나게 됩니다.
즉, 아래와 같이 (9, 23)의 W는 B로 덧칠됩니다.
... 16 17 18 19 20 21 22 23
1
2 ... B W B W B W B W
3 ... W B W B W B W B
4 ... B W B W B W B W
5 ... W B W B W B W B
6 ... B W B W B W B W
7 ... W B W B W B W B
8 ... B W B W B W B W
9 ... W B W B W B W B
(B는 black, W는 white)
case_black은 (9, 23)을 포함하지 않는 구역과 덧칠하는 횟수가 동일하게 나타납니다.
반대로 case_white라면 (9, 23)은 덧칠되지 않고 W를 유지하게 됩니다.
때문에 덧칠하는 횟수가 31로 감소합니다.
... 16 17 18 19 20 21 22 23
1
2 ... W B W B W B W B
3 ... B W B W B W B W
4 ... W B W B W B W B
5 ... B W B W B W B W
6 ... W B W B W B W B
7 ... B W B W B W B W
8 ... W B W B W B W B
9 ... B W B W B W B W
(B는 black, W는 white)
위와 같은 이유로 저는 2가지 case를 동시에 고려해서 결과를 도출했습니다.
2. 알고리즘
체스판의 패턴을 저장하는 2차원 배열을 선언합니다.
체스판은 2개 행 단위로 동일한 패턴을 지니고 있으므로 2x8 크기의 패턴을 저장하는 char형 2차원 배열이 됩니다.
case_black와 case_white로 나뉘기 때문에 아래와 같이 배열을 선언합니다.
// 체스판 패턴
public static char[][] black = {
{'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
{'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'}
};
public static char[][] white = {
{'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
{'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'}
};
입력되는 MxN 크기의 보드 안에서 8x8 크기의 체스판을 위의 패턴으로 하나씩 대조하게 됩니다.
2차원 행렬 안에 2차원 행렬이 덧붙은 모양새여서 4중 for문을 이용합니다.
아래는 추상적 알고리즘입니다.
// MxN 크기의 보드
for(8x8 체스판을 만들 수 있는 한도의 시작 행) {
for(8x8 체스판을 만들 수 있는 한도의 시작 열) {
...
// 8x8 크기의 체스판
for(8x8 체스판의 행) {
for(8x8 체스판의 열) {
...
// 자른 체스판과 체스판 패턴 비교해서 덧칠 횟수 카운트
}
}
// 덧칠 횟수가 적은 case의 값 저장
}
}
밖의 2중 for문은 잘릴 체스판의 첫 위치를 표기합니다.
안의 2중 for문은 자른 체스판과 체스판 패턴을 비교해서 덧칠 횟수를 카운트합니다.
비교가 끝나면 2가지 case 중에서 적은 값을 answer 변수에 저장합니다.
이를 토대로 코드를 작성하면 아래와 같습니다.
import java.util.Scanner;
public class RepaintingChessBoard_1018 {
// 체스보드 패턴
public static char[][] black = {
{'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
{'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'}
};
public static char[][] white = {
{'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
{'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'}
};
public static void main(String[] args) {
int row, col, answer;
Scanner sc = new Scanner(System.in);
row = sc.nextInt();
col = sc.nextInt();
String[] str = new String[row];
// board 입력
for(int i = 0; i < row; i++) {
str[i] = sc.next();
}
answer = 9999;
// row by col 행렬
// 잘라야 하는 board의 시작 위치로 활용하므로 입력받은 값에 -8까지 동작
for(int i = 0; i <= row-8; i++) {
for(int j = 0; j <= col-8; j++) {
int caseBlock = 0; // case_black에서 덧칠해야 하는 사각형 개수
int caseWhite = 0; // case_white에서 덧칠해야 하는 사각형 개수
int rowIdx = 0; // 체스보드 패턴의 행 idx
// 8 by 8 체스보드
for(int k = i; k < i+8; k++) {
int colIdx = 0; // 체스보드 패턴의 열 idx
for(int l = j; l < j+8; l++) {
// case_black
if(str[k].charAt(l) != black[rowIdx][colIdx])
caseBlock++;
// case_white
if(str[k].charAt(l) != white[rowIdx][colIdx++])
caseWhite++;
}
// 체스보드 패턴의 행 idx 반전
rowIdx = -rowIdx + 1;
}
// case_white, case_black 중에서 작은 값 저장
if(answer > caseBlock)
answer = caseBlock;
if(answer > caseWhite)
answer = caseWhite;
}
}
System.out.println(answer);
}
}
3. 결과
'알고리즘 > BAEKJOON' 카테고리의 다른 글
| [백준 1269] 대칭 차집합 - JAVA (0) | 2022.06.11 |
|---|---|
| [백준 7568번] 덩치 문제 -Java (0) | 2022.02.28 |
| [백준 2231번] 분해합 문제 - Java (0) | 2022.01.25 |
| [백준 2798번] 블랙잭 문제 - Java (0) | 2022.01.18 |
