문제 url:
체스판 다시 칠하기
문제:
🤔 문제 알아보기
해당 문제는 브루트 포스 알고리즘의 문제로, 완전 탐색으로 문제를 해결하는 방법으로 진행한다.
이제 문제를 알아보자
- 먼저, M * N 크기의 보드를 입력받는다.
- 그리고 그 보드 크기에 8 * 8 크기만큼의 체스판을 만드는데, 색깔을 가장 적게 바꾼 횟수를 출력값으로 받고자 한다.
- 여기서 중요한 내용이 존재하는데,
- 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위칸이 횐색일 경우, 하나는 검은색인 경우이다.
- 즉 이 말은, 체스판을 만들 때 첫번 째 색깔이 횐색일 수도, 검은색일 수 있다는 것,
경우의 수가 2가지 존재한다고 생각하면 될 것 같다.
💦 풀이 설계하기
위에서 문제를 알아봤고, 이를 이용해 조금 더 깊게 알아보자,
※그 이전에 우리는 먼저, 입력 받은 크기를 보드. 8 * 8 크기를 체스판이라고 명명하겠다.보드의 움직임을 먼저 그림으로 나타내보겠다.
이런식으로 움직이며, 마지막까지 검색하는 완전 탐색으로 해당 문제를 풀려고 한다.
이런식으로 풀려면 총, 전체를 움직이는 반복문과 8 * 8의 체스판을 검색할 반복문
총 큰 틀에서 봤을 때 반복문이 두 개가 필요할 것으로 보인다.
먼저 전체를 움직이는 반복문 부터 보면,
만약 우리가 10 X 13 크기의 보드를 입력받았다고 가정하자,
즉 행이 10개, 열이 13개인 크기가 생긴건데, 이를 8 * 8 크기의 체스판을 움직여가며 확인할 것이다.
그렇다면 행(10개)은 총 몇번의 반복이 필요하겠는가?
손재주가 좋지않다. 이해 부탁드립니다
행을 움직인다면 그림과 같이 움직일 수 있다.
그렇다면 총 10 - 8번만큼 반복을 할 것인데, 여기서 중요한 것은
최소 크기인 8 * 8 역시 처음에 검색을 진행중인것이기에
정확하게 말하자면 10 - 7번 반복해야 하는 것이다. (이해가 안된다면 그림을 보면 좀 더 수월할 것이다. 현재 그림은 총 3개를 나타낸다.)
보드의 행의 반복 횟수를 알았으니, 열도 똑같이 적용할 수 있을 것이다.
다음은 체스판의 검색 방법에 대해 알아보도록 하겠다.
다들 한번씩 체스를 둔 경험이 있을 것이다. 체스판을 보면 색깔이 (흰 백 흰 백) 이렇게 나오는 것을 봤을 것이다. 이를 생각해서 문제를 풀어 본다면
맨 첫번째 칸(0,0) 이 횐색이면, 그 다음 칸(0,1)은 반드시 검은색이어야한다.
그 후, (1,0) 까지 왔을 때, (0,0)이 흰색이므로 (1,0)은 반드시 검은색이어야 한다.
그렇다면 이제 해당 로직을 이용해서,
만약 현재 위치의 색깔이 검은색이어야 하는데 흰색이라면??? 개수를 +1한다.
이걸 8 * 8 배열을 모두 해준 다음, 가장 작은 값을 저장하도록 한다면? 답을 구할 수 있다.
🐱👤 실제 코드
백문불여일견 직접 코드를 확인하면 이해하기 쉽다.
import java.io.*;
import java.util.StringTokenizer;
public class Main {
// arr를 Main 필드에 전역적으로 두는 이유는
// find 함수에서도 해당 배열을 사용하기 때문
static Boolean[][]arr;
// min_count를 Main 필드에 전역적으로 두는 이유는
// find 함수에서도 해당 배열을 사용하기 때문
// min_count는 모든 체스판에서 나올 수 있는 값들 중 가장 작은 값을 초기화 하는 변수,
static int min_count = 65;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken()); // 가로의 길이
int B = Integer.parseInt(st.nextToken()); // 세로의 길이
// A * B 크기의 보드를 생성
// 왜 Boolean type? : 현재 받는 값은 B 또는 W이다. 즉, true or false로 나타낼 수 있다.
// 그래서 B는 true // w는 false로 나타내려고 한다.
arr = new Boolean[A][B];
// 가로줄 만큼 글자를 입력받느 반복문
for (int i = 0; i < A; i++) {
String word = br.readLine();
// 글자의 문자형이 B이면 arr 배열에 true를, 아니면 false로 초기화
for (int j = 0; j < word.length(); j++) {
if (word.charAt(j) == 'B') {
arr[i][j] = true;
} else {
arr[i][j] = false;
}
}
}
// 더 이상 입력받은 것이 없기 때문에 BufferedReader는 종료
br.close();
// 전체 반복을 위한 반복문(즉 A * B 보드를 8 * 8만큼 전체를 훑기위한)
// i <= A-8를 해주는 이유는 8 * 8배열만큼 뺀 후 추가적으로 진행할 개수만큼 A 또는 B를 움직여야 하기에
// 또한 < 가 아닌 <=를 해주는 이유는 처음에 진행하는 것도 반복에 포함되어야 하기에 <= 로 진행
for (int i = 0; i <= A - 8; i++) {
for (int j = 0; j <= B - 8; j++) {
find(i, j);
}
}
System.out.println(min_count);
}
public static void find(int x, int y) {
// 몇 개가 변경되었는지 확인하기 위한 변수
// 왜 변수가 여기에 위치하냐면, 8 * 8 체스판을 계산할 때마다 세야 하므로 여기서 정의를 해줌
int count = 0;
// x와 y는 현재 체스판이 초기에서 x쪽으로 혹은 y쪽으로 움직였냐를 의미한다.
// 그 후 8 * 8 체스판 크기만큼 계산하기 때문에 현재 위치에 + 8을 해야 마지막점까지 계산이 가능하다.
int end_x_point = x + 8;
int end_y_point = y + 8;
// TF란 현재 위치가 해당 TF의 색을 가지고 있어야 하는 변수를 의미.
// 이 TF 변수를 통해 원본 데이터(arr 배열)에 훼손을 가하지 않고, 알고리즘이 가능한 것이다.
Boolean TF = arr[x][y];
for (int i = x; i < end_x_point; i++) {
for (int j = y; j < end_y_point; j++) {
// 현재 위치가 현재 가지고 있어야 할 색깔과 다를 경우 count++를 진행,
// 즉 바꿔져야 하는 색깔을 의미.
if(arr[i][j] != TF) {
count++;
}
// 다음 TF의 색깔이 진행되어야하는 색을 의미,
// 지금이 W면 다음 정사각형은 B가 되어야 한다는 의미
TF = !TF;
}
// 여기는 가로줄이 변경되기 전에 TF의 색깔을 의미,
// 현재 만약 가로줄 1번이며, 2번으로 넘어가야 한다고 가정하면
// 2번줄의 첫번 쨰 칸은 1번줄 마지막 칸과 색깔이 같아야 함으로 로직을 진행
TF = !TF;
}
// 왜 다시 카운트에다가 재 초기화??
// 현재 카운트는 만약 첫번째 칸이 보드와 같은 색일 때를 나타내는 개수를 의미.
// 64 - count는 만약 첫번째 칸이 B이고 보드가 W
// 즉, 내가 만드려는 체스판의 첫번쨰 색깔과 보드의 첫번 째 색깔이 다를경우 64- count로 계산할 수 있다.
// ※ 64는 체스판이 8 * 8크기이기 때문이다.
count = Math.min(count, 64 - count);
min_count = Math.min(min_count, count);
}
}
필자 역시, 코드를 치다 치다 틀려 타 블로그 글을 참조하며 한다고, 주석이 많다.
이를 하나씩 까보며 분석해보도록 하겠다.
😁 코드 해석
// arr를 Main 필드에 전역적으로 두는 이유는
// find 함수에서도 해당 배열을 사용하기 때문
static Boolean[][]arr;
// min_count를 Main 필드에 전역적으로 두는 이유는
// find 함수에서도 해당 배열을 사용하기 때문
// min_count는 모든 체스판에서 나올 수 있는 값들 중 가장 작은 값을 초기화 하는 변수,
static int min_count = 65;해당 코드는 Main 클래스 필드에서 전역적으로 이용하기 위해 정의한 변수이다.
static Boolean[][]arr은 추후 b는 true, w는 false를 담기 위해 사용
static int min_count = 65은 체스판에 있는 칸은 총 64개로, 65는 즉 나올 수 없는 값이기 때문에 65로 선언.
// A * B 크기의 보드를 생성
// 왜 Boolean type? : 현재 받는 값은 B 또는 W이다. 즉, true or false로 나타낼 수 있다.
// 그래서 B는 true // w는 false로 나타내려고 한다.
arr = new Boolean[A][B];
// 가로줄 만큼 글자를 입력받느 반복문
for (int i = 0; i < A; i++) {
String word = br.readLine();
// 글자의 문자형이 B이면 arr 배열에 true를, 아니면 false로 초기화
for (int j = 0; j < word.length(); j++) {
if (word.charAt(j) == 'B') {
arr[i][j] = true;
} else {
arr[i][j] = false;
}
}
}arr= new Boolean[A][B]은 아까 전역적으로 선언한, arr 변수이며
여기에는 보드의 크기만큼 2차원 배열을 생성해주는데,
이 변수를 통해, 나중에 입력받는 보드 값들을 b는 true, w는 false로 저장한다.
그 밑의 반복문은 보드판에 있는 값을 입력받는 것으로,
입력값을 받은 후, 해당 값의 인덱스 값이 B면 true로 , w면 false로 2차원 배열에 저장한다.
// 전체 반복을 위한 반복문(즉 A * B 보드를 8 * 8만큼 전체를 훑기위한)
// i <= A-8를 해주는 이유는 8 * 8배열만큼 뺀 후
// 추가적으로 진행할 개수만큼 A 또는 B를 움직여야 하기에
// 또한 < 가 아닌 <=를 해주는 이유는 처음에 진행하는 것도 반복에 포함되어야 하기에 <= 로 진행
for (int i = 0; i <= A - 8; i++) {
for (int j = 0; j <= B - 8; j++) {
find(i, j);
}
}
System.out.println(min_count);이는 문제를 알아볼 때, 말했던 전체 보드를 훑기위한 반복문이다.
아까 그림으로 표현했듯이. 8 * 8 크기이므로 8을 뺴주는데, <=를 해준 이유는 처음에 검색하는 8 * 8 배열도 반복에 포함하기 때문이다.
그 후, 가장 작은 값을 반환한다.
아래는 find 메서드에 대해 설명해보겠다.
public static void find(int x, int y) {
// 몇 개가 변경되었는지 확인하기 위한 변수
// 왜 변수가 여기에 위치하냐면,
// 8 * 8 체스판을 계산할 때마다 세야 하므로 여기서 정의를 해줌
int count = 0;
// x와 y는 현재 체스판이 초기에서 x쪽으로 혹은 y쪽으로 움직였냐를 의미한다.
// 그 후 8 * 8 체스판 크기만큼 계산하기 때문에
// 현재 위치에 + 8을 해야 마지막점까지 계산이 가능하다.
int end_x_point = x + 8;
int end_y_point = y + 8;
// TF란 현재 위치가 해당 TF의 색을 가지고 있어야 하는 변수를 의미.
// 이 TF 변수를 통해 원본 데이터(arr 배열)에 훼손을 가하지 않고,
// 알고리즘이 가능한 것이다.
Boolean TF = arr[x][y];먼저 find 메서드는 아까 이전의 전체 틀의 i와 j를 인수값으로 받는다.
end_x_point 와 end_y_point 변수는
8 * 8 배열이므로 8번째까지 가야 하기에 8을 더하는데,
여기서 x + 8 , y + 8인 이유는
전체 틀이 움직일 때 마다 시작점이 x 혹은 y값 만큼 달라지기 때문이다.
Boolean TF는 현재 8 * 8의 배열 중, 시작점을 받는다.
이 값을 이용해 그 다음 칸이 어떤 색깔이 되어야 하는지를 확인할 수 있다.
필자 같은 경우 처음에 풀 때, 만약 true, false 이런식으로 값을 변경하면
원본값이 훼손될 우려가 있어 배열은 복사하여 사용했는데,
이런식으로 TF를 이용해서 값을 확인하니 그럴 필요가 없어져 충격이었다.
이는 나중에 원본 코드와 함께 다시 설명하겠다.for (int i = x; i < end_x_point; i++) {
for (int j = y; j < end_y_point; j++) {
// 현재 위치가 현재 가지고 있어야 할 색깔과 다를 경우 count++를 진행,
// 즉 바꿔져야 하는 색깔을 의미.
if(arr[i][j] != TF) {
count++;
}
// 다음 TF의 색깔이 진행되어야하는 색을 의미,
// 지금이 W면 다음 정사각형은 B가 되어야 한다는 의미
TF = !TF;
}
// 여기는 가로줄이 변경되기 전에 TF의 색깔을 의미,
// 현재 만약 가로줄 1번이며, 2번으로 넘어가야 한다고 가정하면
// 2번줄의 첫번 쨰 칸은 1번줄 마지막 칸과 색깔이 같아야 함으로 로직을 진행
TF = !TF;
}
// 왜 다시 카운트에다가 재 초기화??
// 현재 카운트는 만약 첫번째 칸이 보드와 같은 색일 때를 나타내는 개수를 의미.
// 64 - count는 만약 첫번째 칸이 B이고 보드가 W
// 즉, 내가 만드려는 체스판의 첫번쨰 색깔과 보드의 첫번 째 색깔이 다를경우 64- count로 계산할 수 있다.
// ※ 64는 체스판이 8 * 8크기이기 때문이다.
count = Math.min(count, 64 - count);
min_count = Math.min(min_count, count);
}맨 처음 if문을 보자
if(arr[i][j] != TF) {
count++;
}이 로직은 현재 TF(현재 위치에 와야하는 색깔)가 현재 보드의 색깔과 다르면,
count++을 한다.
이 말은 해당 칸의 색깔을 변경해야 한다는 의미.
그 후 TF = !TF를 통해 그 다음에 나와야 할 색깔을 초기화 해준다.
(현재 색깔이 b라면 다음 색은 w가 나와야 한다는 의미)
열에 대한 for문이 완료 되면 또 다시 TF = ! TF를 해주는데,
이는 다음 행의 색깔은 이전 행의 마지막 칸의 색깔과 동일해야 하기 때문에
해당 로직을 구현한 것이다.
count = Math.min(count, 64 - count);
min_count = Math.min(min_count, count);위의 코드가 이제 개수를 세는 변수인데,
카운트 변수에 왜 count와 64- count 중, 최솟값을 초기화 시키냐면
위에 문제를 알아봤을 떄, 체스판의 맨 첫번째 칸이 검은색일 수도 흰색일 수도 있다고 했다. 즉 경우의 수가 두 가지가 존재한다.
그래서, 그냥 count는 체스판의 시작색과 보드의 색깔과 동일했을 때의 카운트 수이며,
64 - count는 그 반대일 때의 카운트 수가 된다.
그런 다음 min_count 변수에 현재 가장 작은 최솟값을 초기화 하는 로직이다.
이상으로 코드 리뷰를 마치겠다.
🤢 회고
문제 로직을 이해하는 데, 그렇게 많은 시간을 쓰지는 않았다. 그렇지만 이를 구현하는데 좀 막막했다.
현재 다른 블로그를 참고하며 문제를 진행했기에 매끄럽게 풀렸지만, 이전 코드는 중구난방이다.
해당 코드는 문제는 풀었지만 결국, 체스판 색의 첫번 째가 검은색인지 흰색인지의 경우의 수를 풀지 못해 창고행이 되어 버렸다.
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int X = Integer.parseInt(st.nextToken()); //x 개수
int Y = Integer.parseInt(st.nextToken()); //y 개수
char[][] chess = new char[X][Y];
char[][] chess_clone = new char[X][Y];
for(int i = 0; i < X; i++) {
String bw = br.readLine();
chess[i] = bw.toCharArray();
}
int min_count = X * Y;
//완전 탐색을 하기 위한 전체 반복문
// X좌표 전체를 탐색하기 위한 큰 반복문
for (int m = 0; m <= X - 8; m++) {
// y좌표 전체를 탐색하기 위한 큰 반복문
for (int n = 0; n <= Y - 8; n++) {
// 깊은 복사를 진행
for(int i = 0; i < chess.length; i++) {
chess_clone[i] = chess[i].clone();
}
int count = 0;
for(int i = m; i < m + 8-1; i++) {
for (int j = n; j < n + 8-1; j++) {
if (chess_clone[i][j] == chess_clone[i][j+1] && chess_clone[i][j] == 'B') {
chess_clone[i][j+1] = 'W';
count++;
} else if ((chess_clone[i][j] == chess_clone[i][j+1] && chess_clone[i][j] == 'W')) {
chess_clone[i][j+1] = 'B';
count++;
}
if (chess_clone[i][j] == chess_clone[i+1][j] && chess_clone[i][j] == 'B') {
chess_clone[i+1][j] = 'W';
count++;
} else if ((chess_clone[i][j] == chess_clone[i+1][j] && chess_clone[i][j] == 'W')) {
chess_clone[i+1][j] = 'B';
count++;
}
if(chess_clone[m+7][n+7] == 'W' && chess_clone[m+7][n+7] == chess_clone[m+7-1][n+7] && chess_clone[m+7][n+7] == chess_clone[m+7][n+7-1] ) {
chess_clone[m+7][n+7] = 'B';
count++;
} else {
chess_clone[m+7][n+7] = 'W';
count++;
}
}
}
count = Math.min(count, 64 - count);
min_count = Math.min(min_count, count);
}
}
System.out.println(min_count);
}
}
아까 TF 변수를 처음 봤을 떄 머리가 띵했는데, 그 이유가
필자는 배열을 아래처럼 복사해서 사용했기 때문이다.// 깊은 복사를 진행 for(int i = 0; i < chess.length; i++) { chess_clone[i] = chess[i].clone(); }즉 원본 데이터가 훼손 될 것이라고 판단하여 했던 clone이.. 오히려 변수 하나로 대체할 수 있는 로직이라는 것이었다.
해당 문제를 풀면서 문제 이해력도 키워야 겠고, 구현이 더러우면 추후 리팩토링이나 이해하기가 어렵다는 것을 또 한번 느꼈다.
계속해서 타 블로그를 참조하며 더 나은 코드 더 좋은 방법으로 리팩토링하는 방법과 노하우들을 배워 나가야겠다.
💜 참고 자료
[백준] 1018번: 체스판 다시 칠하기 - JAVA Stranger's LAB
-> 늘 고맙습니다.
