[백준](Python, TypeScript) 1018번 : 체스판 다시 칠하기

https://www.acmicpc.net/problem/1018

1. 풀이

- 주어진 행렬을 8x8로 자른 뒤, 체스판이 되도록 칠하는 문제다.

- 체스판의 모양은 항상 2개밖에 없다 : 행렬의 좌측 상단이 흰색이거나, 검은색이거나.

 

즉,

1) 주어진 행렬의 가장 왼쪽 상단의 점을 보고,

2) 해당 위치를 기준으로 8x8 행렬에 대해 왼쪽 상단의 점이 흰색일 때 고쳐야 할 칸의 개수와 검은색일 때 고쳐야 할 칸의 개수를 구한 뒤, 그 중 작은 값만 가져간다.

 

- 행, 열의 개수가 50개 이하이므로 최대로 고쳐야 할 칸의 수는 1250개일 것이다. 그래서 최소 칸의 개수를 1251로 놓고 시작했다.

- 2차원 행렬이라 변수를 설정할 때 N, M이나 i, j로 놓으면 헷갈리는 경우가 많은데, 나 같은 경우는 row, col로 변수명을 설정하면 그래도 좀 직관적으로 들어오기는 했다.

 

1.1. Python

import sys

# 열의 개수 M 행의 개수 N
N, M = map(int, sys.stdin.readline().split())
matrix = [sys.stdin.readline().strip() for _ in range(N)]

def B_Matrix(row, col):
    """
    왼쪽 상단이 검정색일 때 수정해야 할 칸의 개수를 구함
    """
    need_to_fix = 0

    for r in range(8):
        for c in range(8):
            cell_value = matrix[row + r][col + c]
            if (r + c) % 2 == 0 and cell_value == 'W':
                need_to_fix += 1elif (r + c) % 2 == 1 and cell_value == 'B':
                need_to_fix += 1
    
    return need_to_fix
    
def W_Matrix(row, col):
    """
    왼쪽 상단이 흰색일 때 수정해야 할 칸의 개수를 구함
    """
    need_to_fix = 0

    for r in range(8):
        for c in range(8):
            cell_value = matrix[row + r][col + c]
            if (r + c) % 2 == 0 and cell_value == 'B':
                need_to_fix += 1elif (r + c) % 2 == 1 and cell_value == 'W':
                need_to_fix += 1
    
    return need_to_fix


#  전체 순회 갯수 : (M-8+1)*(N-8+1)
ans = 1251
for i in range(N - 7):
    for j in range(M - 7):
        min_to_fix = min(B_Matrix(i, j), W_Matrix(i, j))
        ans = min(ans, min_to_fix)

print(ans)

1.2. TypeScript

const input: string[] = require('fs').readFileSync('dev/stdin').toString().split('\n');

const [M, N] = input[0].split(' ').map(Number)
const matrix: string[] = input.slice(1) // 2번째 원소 ~ 끝까지 슬라이스

const Wmatrix = (row: number, col: number): number => {
    let needToFix: number = 0;
    for (let r=0;r<8;r++) {
        for (let c=0;c<8;c++) {
            const cellValue = matrix[row + r][col + c]
            if ((r + c) % 2 === 0 && cellValue === 'B') {
                needToFix += 1
            } else if ((r + c) % 2 === 1 && cellValue === 'W') {
                needToFix += 1
            }
        }
    }
    return needToFix
}

const Bmatrix = (row: number, col: number): number => {
    let needToFix: number = 0;
    for (let r=0;r<8;r++) {
        for (let c=0;c<8;c++) {
            const cellValue = matrix[row + r][col + c]
            if ((r + c) % 2 === 0 && cellValue === 'W') {
                needToFix += 1
            } else if ((r + c) % 2 === 1 && cellValue === 'B') {
                needToFix += 1
            }
        }
    }
    return needToFix
}

let ans = 1251;
for (let i=0;i<M-7;i++) {
    for (let j=0;j<N-7;j++) {
        ans = Math.min(ans, Wmatrix(i,j), Bmatrix(i, j))
    }
}

console.log(ans)