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

퀸스컴뱃 봐야하는데..

 

요즘 1일 1문제 푸는 재미 들린 필자.

오늘은 체스판 다시 칠하기를 풀었다.

 

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

1018번: 체스판 다시 칠하기

 

알고리즘 분류는 부르트포스이다.

(내 맘대로 풀라는 문제)

사실 이런 문제를 좋아한다.

왜냐하면 특정 알고리즘을 이용해야만 풀리는 문제는 좀.. 창의력을 막는 기분이다.

이런 문제 특징이 굉장히 다양한 방법으로 풀 수 있기 때문에 다양한 측면을 생각하여 푸는 능력을 기를 수 있다는 것이다.

 

이 문제는 두가지가 중요하다.

1. 어떻게 자를 것인가.

2. 어떻게 색칠할 것인가.

 

첫번째 문제는 내가 이 문제를 다가간 관점은 하나씩 리스트를 슬라이싱해서 그 중 바꿔야하는 색깔이 가장 적은 것을 선택하는 식으로 다가갔다.

 

그래서 일단 자르고 보기 시작했다.

 

import sys
n, m = map(int, sys.stdin.readline().split())
board = [sys.stdin.readline().rstrip()
         for i in range(n)]

 

일단 입력을 예쁘게 받아오고

어떻게 자를지 생각해봤는데 매우 많은 for문을 돌려야 할 것 같아서 함수로 나눠서 코드를 짰다.

그렇게 짠 첫번째 함수가 바로 보드를 원하는 위치에서 자르는 함수이다.

 

def new_board(x, y):
    new = [board[dy][x:x+8] for dy in range(y, y+8)]
    return new

 

매우 간단하다.

x, y 좌표에서 부터 8*8의 크기만큼 자른 보드를 반환하는 함수이다.

 

예를들어 10 * 13의 보드가 입력을때 

 

BBBBBBBBWBWBW

BBBBBBBBBWBWB

BBBBBBBBWBWBW

BBBBBBBBBWBWB

BBBBBBBBWBWBW

BBBBBBBBBWBWB

BBBBBBBBWBWBW

BBBBBBBBBWBWB

WWWWWWWWWWBWB

WWWWWWWWWWBWB

 

x=2, y=1이면

 

앞에 한줄을 자른 두번째 줄부터 열번째 줄까지 남기고 남은건 다 다른다.

그리고 세로도 왼쪽으로 부터 2개의 글자는 다 자른다.

 

BBBBBBBWBWB

BBBBBBWBWBW

BBBBBBBWBWB

BBBBBBWBWBW

BBBBBBBWBWB

BBBBBBWBWBW

BBBBBBBWBWB

WWWWWWWWBWB

 

이렇게 예쁜 8*8의 체스판을 가져올 수 있게된다.

 

이걸 이제 x와 y를 모든 경우의 수만큼 대입해서 잘라서 만들수 있는 모든 경우의 판을 가져온다.

 

 

두번째문제는 정말 여러 방법이 있다.

B와 W의 개수 차이를 이용할 수 있지 않을까?

(0,0)에 w가 온 판과 b가 오는 판, 두가지의 판만 존재한다는 걸 이용할 수 있지않을까?

 

고민 후 후자의 방식을 선택했다.

각 좌표에 칠해져 있는 색깔이 (0,0)에 w가 온 판에 맞는 색인지 b가 온 판에 맞는 색인지를 따져서 현재 있는 색이 맞는 판에 카운트를 올린다.

그 후 두 판 중 더 높은 수를 갖고 있는 판이 색을 최소로 변경하는 판이라 여긴다.

총 칸수 64 - 옳바른 색의 칸 수 = 바꿔야하는 칸 수

 

이런식으로 생각 후 코드를 짰다.

 

def wb(b):
    w_cnt = 0
    b_cnt = 0
    for y in range(len(b)):
        for x in range(len(b[y])):
            if y % 2 == 0:
                if x % 2 == 0:
                    if b[y][x] == 'W':
                        w_cnt += 1
                    else:
                        b_cnt += 1
                else:
                    if b[y][x] == 'B':
                        w_cnt += 1
                    else:
                        b_cnt += 1
            else:
                if x % 2 == 0:
                    if b[y][x] == 'B':
                        w_cnt += 1
                    else:
                        b_cnt += 1
                else:
                    if b[y][x] == 'W':
                        w_cnt += 1
                    else:
                        b_cnt += 1
    if w_cnt < b_cnt:
        return 64-b_cnt
    elif w_cnt > b_cnt:
        return 64-w_cnt
    else:
        return 32

 

 

그 후 이 두가지 함수를

for y in range(n-7):
    for x in range(m-7):
        new = new_board(x, y)
        cnt = wb(new)
        if cnt < mini:
            mini = cnt

 

이렇게 자를 수 있는 모든 경우의 수를 돌려보기 위해 2중 for문을 돌려서 가장 작은 수를 가져왔다.

 

 

참고로 혼자 생각해서 푼 것으로 모범답안과는 거리가 멀다.

다른 사람 풀이는 보통 안보는 편이라 다들 어떻게 풀었는지 잘 모른다..