문제 설명
8*8 크기의 체스판을 완전탐색합니다. 즉, 크기가 8*8보다 더 큰 경우 위치를 옮겨가며 확인해야 합니다.
왼쪽부터 오른쪽으로 스캔하듯 모두 훑어줍니다. 가로 탐색이 끝났다면 이제 세로축을 한 칸 증가시켜야겠죠?
한 칸 내린후 위와 동일하게 오른쪽으로 쭉 가야합니다.
어떤 로직인지 이해 하셨나요? 그럼 최종적으로 아래 그림처럼 탐색을 마칩니다.
자. 이제 위와같은 체스판이 아닌 흑백이 섞인(또는 뒤죽박죽) 체스판 모양이 입력됩니다.
여기서 정상적인 체스판과 비교를 했을 때, 몇 개의 칸을 다시 색칠해야 하는지를 출력합니다.
단, 위의 모든 범위중 최소값이어야 합니다.
저는 8*8크기의 정상적인 체스판을 미리 만들고 탐색을 하며 비교하는 방식으로 구현했습니다.
소스 코드
9개월 전의 제가 작성한 코드를 함께 첨부합니다. 소스코드 자체는 짧아졌지만 가독성과 실행시간 측면에서는 큰 차이가 없는 것 같네요.
9개월간 큰 변화가 없다는게 씁쓸하면서도 역시 자기 자신과의 싸움이 제일 힘든 것 같습니다 ㅠㅠ 더 열심히 해야겠어요.
Python (20.04.20)
n,m = map(int,input().split())
board = [list(input()) for _ in range(n)]
boardW = [[0]*m for _ in range(n)]
boardB = [[0]*m for _ in range(n)]
flag = 'W'
for i in range(n):
for j in range(m):
if board[i][j]==flag:
boardW[i][j]=0
boardB[i][j]=1
else:
boardW[i][j]=1
boardB[i][j]=0
if j+1!=m:
flag = 'W' if flag=='B' else 'B'
if m%2!=0:
flag = 'W' if flag=='B' else 'B'
res=99999999
for i in range(n):
for j in range(m):
if j+8<=m and i+8<=n:
sumW=0
sumB=0
for w in boardW[i:i+8]:
sumW+=sum(w[j:j+8])
for b in boardB[i:i+8]:
sumB+=sum(b[j:j+8])
res=min(sumW,sumB,res)
print(res)Python (21.01.30)
import sys
input = sys.stdin.readline
N,M = map(int,input().rstrip().split())
comp = [['W' if (i+j)%2==0 else 'B' for i in range(N)] for j in range(M)]
field = [list(input().rstrip()) for _ in range(N)]
answer = 2501
for b_i in range(N-7):
for b_j in range(M-7):
cnt = [0,0]
for h in range(b_i,b_i+8):
for w in range(b_j,b_j+8):
if comp[h-b_i][w-b_j]!=field[h][w]:cnt[0]+=1
else:cnt[1]+=1
minNum = min(cnt[0],cnt[1])
if answer > minNum:answer=minNum
print(answer)Java8
package boj1018;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
static char[][] field;
static char[][] comp;
static int func(int W,int H) {
int cnt1=0, cnt2=0;
for(int h =H;h<H+8;h++) {
for(int w=W;w<W+8;w++) {
//첫 칸이 B인 경우
if(field[h][w]==comp[h-H][w-W])cnt1++;
//첫 칸이 W인 경우
if(field[h][w]!=comp[h-H][w-W])cnt2++;
}
}
return Math.min(cnt1, cnt2);
}
static void solve() throws IOException{
String args[] = bf.readLine().split(" ");
int height = Integer.parseInt(args[0]);
int width = Integer.parseInt(args[1]);
field = new char[height][width];
for(int i =0;i<height;i++)
field[i] = bf.readLine().toCharArray();
int answer = 2501;
for(int y =0;y+8<=height;y++)
for(int x =0;x+8<=width;x++)
answer = Math.min(func(x,y),answer);//더 작은 값으로
System.out.println(answer);
}
public static void main(String[] args) throws IOException{
comp = new char[8][8];
for(int i =0;i<8;i++)
for(int j =0;j<8;j++)
comp[i][j]=(i+j)%2==0?'W':'B';
solve();
}
}