[파이썬/Python] 백준 1018번 체스판 다시 칠하기

[파이썬/Python] 백준 1018번 체스판 다시 칠하기

1018번: 체스판 다시 칠하기

---

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

 

해설

1. M * N 체스판이 있으면, 우리는 그 중 8 * 8 크기만 탐색해야 한다.

인덱스 0~7까지 탐색후 처음과 끝을 1씩 증가하면서 M, N 의 끝까지 탐색한다.

 

2. 그 지정한 범위의 8 * 8 안에서 인덱스를 돌면서, B인지 W인지를 체크한다.

index = 0 을 기준점으로,

시작이 W인 경우를 cnt1, 시작이 B인 경우를 cnt2로 가정하여 체크한다.

만약 짝수가 B라면면 cnt1 이 체크되고, W이면 cnt2가 체크된다.

홀수가 W라면 cnt1이 체크되고, B이면 cnt2가 체크된다.

 

3. cnt1, cnt2 중 최소값을 res에 저장한다.

 

4. res 에는 M * N 을 돌면서 나온 최소값들이 저장되어있다.

그 중에서 최소 값이 다시 칠해야하는 최소 개수이다.

 

코드

import sys

N, M = map(int, sys.stdin.readline().split())

board = [sys.stdin.readline().strip() for _ in range(N)]
res = []

for i in range(N-7):
    for j in range(M-7):
        cnt1 = 0
        cnt2 = 0
        for k in range(i, i+8):
            for l in range(j, j+8):
                if (k+l) % 2 == 0:
                    if board[k][l] != 'W':
                        cnt1 += 1
                    else:
                        cnt2 += 1
                else:
                    if board[k][l] != 'B':
                        cnt1 += 1
                    else:
                        cnt2 += 1
        res.append(min(cnt1, cnt2))

print(min(res))

 

풀이

import sys

N, M = map(int, sys.stdin.readline().split())

board = [sys.stdin.readline().strip() for _ in range(N)]
res = []

1. M, N 을 입력 받고 M*N 크기의 보드를 생성한다. res 는 최소값을 저장

 

 

for i in range(N-7):
    for j in range(M-7):
        cnt1 = 0
        cnt2 = 0
        for k in range(i, i+8):
            for l in range(j, j+8):

2.

i, j 는 8 * 8 의 기준을 정해주고,

k,l 은 8 * 8 의 시작점부터 끝점까지를 돌면서

W인지, B인지 체크한다.

 

for i in range(N-7):
    for j in range(M-7):
        cnt1 = 0
        cnt2 = 0
        for k in range(i, i+8):
            for l in range(j, j+8):
                if (k+l) % 2 == 0: # 짝수
                    if board[k][l] != 'W':
                        cnt1 += 1
                    else:
                        cnt2 += 1
                else: # 홀수
                    if board[k][l] != 'B':
                        cnt1 += 1
                    else:
                        cnt2 += 1

3.

짝수일 경우, W가 아닐 경우 cnt1 체크, B가 아닐 경우 cnt2 체크

홀수일 경우, B가 아닐 경우 cnt1 체크, W가 아닐 경우 cnt2 체크

 

for i in range(N-7):
    for j in range(M-7):
        cnt1 = 0
        cnt2 = 0
        for k in range(i, i+8):
            for l in range(j, j+8):
                if (k+l) % 2 == 0:
                    if board[k][l] != 'W':
                        cnt1 += 1
                    else:
                        cnt2 += 1
                else:
                    if board[k][l] != 'B':
                        cnt1 += 1
                    else:
                        cnt2 += 1
        res.append(min(cnt1, cnt2))

4. 저장된 cnt1, cnt2 중 최소값을 res에 저장(8*8 내에서 최소값)

 

 

print(min(res))

5. M*N 내에서의 최소값 출력

 

피드백

Q. 고칠 필요가 없는 경우에도 카운터가 올라가지 않을까?

A. 시작이 W라 가정하고,
i=0, j=0 일 때,
첫번째 if 문에 걸려서 index1 = 0,
i=0, j=1 일 때, else 문에 걸릴거고
값은 B일테니 index1 = 0
따라서 고칠 필요가 없는 경우에도 카운터는 올라가지 않는다.