백준 1018번 체스판 다시 칠하기 write-up

 

#!/usr/bin/env python3
# coding: utf-8

def set_plate():
    n, m = map(int, input().split())
    plate = []
    for i in range(n):
        row = list(input())
        plate.append(row)
    return n, m, plate


def get_repaint(plate):
    result = []
    row = [ ['W', 'B'] * 4, ['B', 'W'] * 4 ]
    for i in range(2):
        repaint = 0
        for j in range(8):
            check = row[(i + j) % 2]
            for k in range(8):
                if plate[j][k] != check[k]:
                    repaint += 1
        result.append(repaint)

    return min(result)


def solve(n, m, plate):
    result = []
    i = j = 0
    while i <= n - 8:
        j = 0
        while j <= m - 8:
            tmp_plate = [ list(plate[i+k][j:j+8]) for k in range(8) ]
            res = get_repaint(tmp_plate)
            result.append(res)

            j += 1
        i += 1

    return min(result)


def main():
    n, m, plate = set_plate()
    print(solve(n, m, plate))


if __name__ == '__main__':
    main()

 

1. M, N, Plate 변수에 저장하기

def set_plate():
    n, m = map(int, input().split())
    plate = []
    for i in range(n):
        row = list(input())
        plate.append(row)
    return n, m, plate

 

set_plate() 함수를 정의하여 n, m, plate 를 저장한다. plate는 2차원 배열 형식으로 저장했다.

 

 

2. 페인트칠을 할 8x8 판을 정하기

def solve(n, m, plate):
    result = []
    i = j = 0
    while i <= n - 8:
        j = 0
        while j <= m - 8:
            tmp_plate = [ list(plate[i+k][j:j+8]) for k in range(8) ]
            res = get_repaint(tmp_plate)
            result.append(res)

            j += 1
        i += 1

    return min(result)

 

tmp_plate 라는 변수에 (0, 0) 부터 시작해서 n - 8, m - 8 만큼의 plate를 slice 처리하여 저장하고 get_repaint() 함수에 전달한다. get_repaint()는 페인트칠을 해야하는 칸의 개수를 구하는 함수이며 3번에서 후술하겠다. 8X8 판을 만들 수 있는 모든 경우의 수에 get_repaint() 함수로 칸의 개수를 구하고 최솟값을 리턴한다.

 

 

3. 다시 페인트칠할 칸의 개수 구하기

def get_repaint(plate):
    result = []
    row = [ ['W', 'B'] * 4, ['B', 'W'] * 4 ]
    for i in range(2):
        repaint = 0
        for j in range(8):
            check = row[(i + j) % 2]
            for k in range(8):
                if plate[j][k] != check[k]:
                    repaint += 1
        result.append(repaint)

    return min(result)

 

get_repaint() 함수에서는 앞서 8x8 사이즈로 slice 된 임시 plate를 받아서 페인트칠을 해야 할 칸의 개수를 구한다. 임시 plate의 (0, 0)이 'W'인 경우와 'B'인 경우를 나눠서 검사한다. 그리고 배열에 저장하여 최솟값을 리턴한다.