[Baekjoon] 1018 체스판 다시 칠하기

[문제]

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

1018번: 체스판 다시 칠하기

M * N 보드에서 나올 수 있는 8 * 8 크기의 보드 중 최소한으로 색을 칠해 체스판으로 만드는 경우의 색을 칠할 칸의 수를 출력하는 프로그램을 만드는 문제.

 

입력받은 체스판을 이렇게 만드는 것이 목표. (또는 W, B가 반전된 채로)

[입력]

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

 

[출력]

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

 

0. 예제

예제를 잠깐 살펴보면,

여기서 입력받은 체스판은 중간에 W 하나가 B로 잘못 나와 있다. 이를 확인해서 제대로 다시 칠할 때의 최소 횟수를 구하는 문제.

 

1. 입력받기

먼저, 입력부 코드는 다음과 같다.

 

처음에 M과 N을 입력받고, 다음 M개줄에서 체스판을 입력받으므로

import sys
m, n = map(int, input().split())
board = []
for i in range(m):
    board.append(sys.stdin.readline().strip('\n'))

이렇게 하면 board에 받은 입력을 이용해 2차원 리스트처럼 쓸 수 있는 객체가 만들어진다.

 

2. 반복하기

이제 총 몇 번 반복해야 하는지를 생각해야 하는데,

먼저 다음과 같은 m * n board를 생각해 보자.

먼저 가로 반복부터 생각해보면

단순하게 생각하면 n - 8번 반복하면 되지만, n = 8일 경우에는 1번 실행해야 하므로 n - 8 + 1번(n - 7번) 반복하면 된다.

세로도 마찬가지로 m - 8 + 1 (m - 7) 번 반복하면 된다.

 

그리고 그 안에서 체스판(8 * 8)의 칸을 확인하므로 이중 for문을 또 넣어주면 된다.

 

이를 코드로 만들면

for i in range(m - 8 + 1):
    for j in range(n - 8 + 1):
    	for y in range(8):
        	for x in range(8):

일단 이렇게 된다.

 

3. 고쳐야 하는 횟수 체크하기

그러면 어떻게 틀린 칸을 체크해야 할까?

 

먼저 처음 시작하는 칸(왼쪽 위의 칸)을 기준으로 if문을 사용해 처음 칸이 B일 때랑 W일 때의 경우를 나눠줄 수도 있지만, 그러면 너무 귀찮아진다.

 

그래서 홀수와 짝수처럼 번갈아가며 B와 W가 나오므로 나머지 연산을 이용해 칸마다 카운팅을 하며 나머지 연산을 이용하는 방법을 사용해 보자.

먼저 수를 카운팅 하면 다음과 같다.

 

이때 나머지 연산을 적용시키면

이렇게 된다.

이때 0과 1이 칸마다 같은 이유는 열의 길이가 짝수라서 0과 1이 빠짐없이 반복되기 때문이다.

하지만 우리가 원하는 모양은 이런 모양이 아닌, 다음 모양이다.

따라서 이를 교차시켜 주기 위해서는 그냥 카운팅 된 수만 사용할 것이 아닌 y좌표도 이용해 주어야 한다.

이를 코드로 만들면 다음과 같다.

checker = 'BW'
min = -1
for i in range(m - 8 + 1):
    for j in range(n - 8 + 1):
        cnt = 0
        problem = 0
        for y in range(8):
            for x in range(8):
                if board[i + y][j + x] != checker[(cnt + y)% 2]:
                    problem += 1
                cnt += 1

cnt에 카운팅 된 값을 저장하고, y를 더해 열이 바뀔 때마다 y도 1씩 중가함을 더해 1씩 엇갈리게 만들었다.

 

그리고 0과 1이 반복되는 것을 이용하여 checker이라는 변수에서 인덱싱을 이용해 B와 W을 쉽게 오갈 수 있게 했다.

 

4. 추가 문제 해결

그런데, 시작하는 첫 칸과 코드에서 체크하는 B/W가 하나씩 엇갈리면 어떻게 될까?

그렇다면 이론상 최대 64칸을 전부 다시 칠해야 하는 결과를 반환할 수도 있다.

 

이런 말도 안 되는 경우를 배제하기 위해, 칠해야 하는 칸의 개수(problem)가 32칸을 넘어가면, 64에서 빼주는 코드를 추가하면 마무리가 된다.

if problem > 32:
    problem = 64 - problem
if min == -1 or min > problem:
    min = problem

 

최종 코드는 다음과 같다.

import sys
m, n = map(int, input().split())
board = []
for i in range(m):
    board.append(sys.stdin.readline().strip('\n'))

checker = 'BW'
min = -1
for i in range(m - 8 + 1):
    for j in range(n - 8 + 1):
        cnt = 0
        problem = 0
        for y in range(8):
            for x in range(8):
                if board[i + y][j + x] != checker[(cnt + y)% 2]:
                    problem += 1
                cnt += 1
        if problem > 32:
            problem = 64 - problem
        if min == -1 or min > problem:
            min = problem
print(min)

 

5. 총평

필자의 문제 풀이법의 특징이라면 if문을 사용하지 않고, 나머지 연산과 problem을 64에서 빼주는 방식을 사용했다는 점이다.

 

구글에 검색해 보면 필자 말고도 다른 분들의 코드도 있을 건데, 필자는 필자만의 방식으로 문제를 풀어보고 싶어 이런 방법을 사용했다.

 

혹시 비슷한 방법이나 더 효율적인 방법이 있다면 댓글로 알려주길 바란다.