백준 1018 체스판 다시 칠하기 풀이 python, java

문제로이동

1018번: 체스판 다시 칠하기

---

목차

 

---

Python, 9개월 전의 나와 오늘의 나

Java8

---

문제 설명

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();
	}
}