[백준]1018. 체스판 다시 칠하기 (java, python)

📄 링크

체스판 다시 칠하기

---

💡 문제 분석

W로 시작할 때와, B로 시작할 때를 나누어서 모든 경우를 전부 대조해봅니다

• 시간 복잡도 = O(M * N * 8 * 8)

---

⌨️ 코드

JAVA

import java.util.*;

public class Q1018 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] map = new String[50];
        int N = sc.nextInt();
        int M = sc.nextInt();
        for(int i = 0; i < N; i++)
            map[i] = sc.next();
        int ret = 64;
        for(int i = 0; i <= N - 8; i++) {
            for(int j = 0; j <= M - 8; j++) {
                int cnt = 0;
                for(int r = 0; r < 8; r++)
                    for(int c = 0; c < 8; c++)
                        if((r % 2 == c % 2 ? 'W' : 'B') == map[i + r].charAt(j + c))
                            cnt++;
                ret = Math.min(ret, cnt);
                ret = Math.min(ret,  64 - cnt);
            }
        }
        System.out.println(ret);
        sc.close();
    }
}

PYTHON

n, m = map(int, input().split())
arr = [list(input()) for _ in range(n)]
ret = 64
for i in range(n - 7):
    for j in range(m - 7):
        cnt = 0
        for y in range(i, i + 8):
            for x in range(j, j + 8):
                if ('W' if y % 2 == x % 2 else 'B') == arr[y][x]:
                    cnt += 1
        ret = min(ret, cnt)
        ret = min(ret, 64 - cnt)
print(ret)