[백준 1018] 체스판 다시 칠하기 - Python3

[백준 1018] 체스판 다시 칠하기 - Python3

<문제>

- M*N 사이즈의 보드에서 8*8의 체스판을 잘라서 만드려고 한다.

- 체스판은 한 줄에 검은색, 흰색이 번갈아서 칠해져 있으며 이웃한 상,하,좌,우로 이웃한 면은 서로 다른 색이다.

- 8*8로 잘라낸 체스판이 완벽한 색을 갖도록 색을 다시 칠한다고 할 때 칠하는 면의 최소 개수를 구한다.

 

<입력>

첫째 줄 : N, M (8 <= N,M <= 50인 자연수)

둘째 줄부터 N개의 줄 : 보드의 각 행의 색칠 상태 (B는 검정, W는 흰색)

 

<출력>

체스판의 면을 최소로 칠하는 개수를 출력한다.

 

 

<풀이>

(1)

알고리즘의 순서는 다음과 같이 짰다.

1. 주어진 보드에서 8*8 사이즈의 체스 판을 리스트에 넣는다.

2. 그 리스트에서 색을 칠해야하는 개수를 판별해서 리턴한다.

3. 리턴된 개수를 최소 횟수인지 판별한 후 모든 과정이 끝나고 횟수를 출력한다.

1번을 코드화하기 위해서 8*8의 틀을 옮기되 인덱스 오류를 범하지 않도록 조절해서 코딩했다.

N,M = map(int,input().split())
plate=[]
for _ in range(N):
    plate.append(input())
# chess : 8*8 크기의 리스트
def plate_check(chess):
    count = 0
    B_start = 'BWBWBWBW'
    W_start = 'WBWBWBWB'
    for i in range(8):
        for j in range(len(chess[i])):
            if chess[0][0]=='B':
                if i%2==0:
                    if chess[i][j] != B_start[j]:
                        count += 1
                else:
                    if chess[i][j] != W_start[j]:
                        count += 1
            else:
                if i%2==0:
                    if chess[i][j] != W_start[j]:
                        count += 1
                else:
                    if chess[i][j] != B_start[j]:
                        count += 1
    return count
change_count=0
for i in range(len(plate)-7):
    for j in range(len(plate[i])-7):
        chess_plate = []
        chess_plate.append(plate[i][0+j:8+j])
        chess_plate.append(plate[i + 1][0+j:8+j])
        chess_plate.append(plate[i + 2][0 + j:8 + j])
        chess_plate.append(plate[i + 3][0 + j:8 + j])
        chess_plate.append(plate[i + 4][0 + j:8 + j])
        chess_plate.append(plate[i + 5][0 + j:8 + j])
        chess_plate.append(plate[i + 6][0 + j:8 + j])
        chess_plate.append(plate[i + 7][0 + j:8 + j])
        count = plate_check(chess_plate)
        if i==0 and j==0:
            change_count = count
        else:
            if count < change_count:
                change_count = count
print(change_count)

8*8의 체스판이 저장된 chess_plate를 판별하는 plate_check 함수에 변수로 전달하고

그 체스판의 가장 왼쪽 위가 'B'인지, 'W'인지에 따라서 체스판의 홀수, 짝수 번째 줄을 판별했다.

이렇게 해서 예시 출력은 다 맞았는데 제출했더니 타임아웃도 아니고 그냥 틀렸다고 나왔다... 쓰읍...

뭐가 문제일까... 고민하다가 백준 질문 게시판에 반례를 찾아냈고 그 반례는 다음과 같았다.

8 9
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBB
BBBBBBBBW
답 : 31
출력 : 32

반례를 보니 문제가 생길만한 구간은 맨 마지막 줄일 거라는 생각이 들었다.

이 반례를 해결하기 위해서 고민하다보니 치명적인 실수를 찾아냈다.

지금의 내 풀이는 8*8로 줄여진 체스판의 가장 왼쪽 위의 색을 기준으로 체스판 전체를 탐색했다.

하지만 왼쪽 위의 색을 고치면서 체스판을 바꾸는 경우를 생각하지 못했다.

당연하게도 왼쪽 위 색을 기준으로 따라가야 색칠하는 횟수가 최소가 될 거라고 생각한 불찰이었다.

알고리즘 분류가 브루트포스 알고리즘인데 빼먹은 사례가 있다니, 그냥 문제 유린 수준...

그래서 코드를 수정했다.

 

(2)

N,M = map(int,input().split())
plate=[]
for _ in range(N):
    plate.append(input())
def plate_check(chess):
    count1, count2 = 0, 0
    B_start = ['BWBWBWBW',
               'WBWBWBWB',
               'BWBWBWBW',
               'WBWBWBWB',
               'BWBWBWBW',
               'WBWBWBWB',
               'BWBWBWBW',
               'WBWBWBWB']
    W_start = ['WBWBWBWB',
               'BWBWBWBW',
               'WBWBWBWB',
               'BWBWBWBW',
               'WBWBWBWB',
               'BWBWBWBW',
               'WBWBWBWB',
               'BWBWBWBW']
    for i in range(8):
        for j in range(len(chess[i])):
            if chess[i][j] != B_start[i][j]:
                count1 += 1
            if chess[i][j] != W_start[i][j]:
                count2 += 1
    return min(count1, count2)
change_count=0
for i in range(len(plate)-7):
    for j in range(len(plate[i])-7):
        chess_plate = []
        chess_plate.append(plate[i][0+j:8+j])
        chess_plate.append(plate[i + 1][0+j:8+j])
        chess_plate.append(plate[i + 2][0 + j:8 + j])
        chess_plate.append(plate[i + 3][0 + j:8 + j])
        chess_plate.append(plate[i + 4][0 + j:8 + j])
        chess_plate.append(plate[i + 5][0 + j:8 + j])
        chess_plate.append(plate[i + 6][0 + j:8 + j])
        chess_plate.append(plate[i + 7][0 + j:8 + j])
        count = plate_check(chess_plate)
        if i==0 and j==0:
            change_count = count
        else:
            if count < change_count:
                change_count = count
print(change_count)

다시 짜면 좀 더 짧게 만들었을지도 모르지만 있는 코드를 수정하려다 보니 노가다식이 됐다.

저런 크기의 이중 리스트 정도면 솔직히 노가다도 아니고 복붙하면 금방 만드니 괜찮지 않나?

(나름의 합리화를 해본다...)

아무튼 수정한 코드는 W로 시작하는 판과 B로 시작하는 판을 만들어서 그 판과 전체를 비교하는 식이다.

하나의 판(chess)을 B_start, W_start로 다 비교해서 얻은 횟수 중에 가장 작은 수만 return했다.

 

<풀이 인증>

영광의(?) '틀렸습니다'... 앞으론 최대한 만나지 않았으면 좋겠다...

 

 

 

문제 출처 : www.acmicpc.net/problem/1018