[알고리즘][파이썬] 백준_1018_체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

 

8×8의 크기의 체스판을 만들어야 하는데,

검은색(B)과 흰색(W)이 번갈아서 칠해져 있어야 한다.

이 규칙에 어긋나는 칸은 규칙에 맞게 색을 칠해야 한다.

8×8 크기의 체스판을 잘라 내었을때,

규칙에 맞지 않아 색을 칠해야 하는 최소 칸 수를 출력해야 한다.

---

제출 전 코드

# 제출전 테스트에서 오답 출력을 발견함
# 31이 정답이나 32가 출력됨
NM = [
'BBBBBBBBBBBBBBBBBBBBBBB',
'BBBBBBBBBBBBBBBBBBBBBBB',
'BBBBBBBBBBBBBBBBBBBBBBB',
'BBBBBBBBBBBBBBBBBBBBBBB',
'BBBBBBBBBBBBBBBBBBBBBBB',
'BBBBBBBBBBBBBBBBBBBBBBB',
'BBBBBBBBBBBBBBBBBBBBBBB',
'BBBBBBBBBBBBBBBBBBBBBBB',
'BBBBBBBBBBBBBBBBBBBBBBW']

# 문자열을 리스트로 변환
lst = []
for i in NM:
    c = []
    for j in i:
        c.append(j)
    lst.append(c)

# 8×8 크기로 잘나내기 함수
def sel(x, y):
    x_lst = []
    for i in range(x, x+8):
        y_lst = []
        for j in range(y, y+8):
            y_lst.append([i, j])
        x_lst.append(y_lst)
    return x_lst

# reference B, W 리스트 생성 함수
def ref(tmp):
    lst = []
    
    def fst_B():
        lst = []
        for i in range(8):
            if i % 2 == 0:
                lst.append('B')
            else:
                lst.append('W')
        return lst

    def fst_W():
        lst = []
        for i in range(8):
            if i % 2 == 0:
                lst.append('W')
            else:
                lst.append('B')
        return lst
    
    if tmp == 'B':
        lst.append(fst_B())
        lst.append(fst_W())
        lst.append(fst_B())
        lst.append(fst_W())
        lst.append(fst_B())
        lst.append(fst_W())
        lst.append(fst_B())
        lst.append(fst_W())
    else:
        lst.append(fst_W())
        lst.append(fst_B())
        lst.append(fst_W())
        lst.append(fst_B())
        lst.append(fst_W())
        lst.append(fst_B())
        lst.append(fst_W())
        lst.append(fst_B())
    
    return(lst)

# 오답을 출력하게 만든 문제의 코드
# 각 리스트와 refrence B 또는 W와 비교 후 색칠 요망 칸 수 리턴
def chk(lst): # lst는 8×8 리스트
    if lst[0][0] == 'B':
        cnt = 0
        r_lst = []
        for i in ref('B'):
            r_lst.append(i)
        for i in range(len(lst)):
            for j in range(len(lst[i])):
                if lst[i][j] != r_lst[i][j]:
                    cnt += 1
        return cnt
    else:
        cnt = 0
        r_lst = []
        for i in ref('W'):
            r_lst.append(i)
        for i in range(len(lst)):
            for j in range(len(lst[i])):
                if lst[i][j] != r_lst[i][j]:
                    cnt += 1
        return cnt

# 모든 경우의 8×8 리스트 생성
t_rst = []
for row in range(len(NM)-7):
    for col in range(len(NM[0])-7):
        rst = []
        tmp = sel(row, col)
        for i in tmp:
            r_tmp = []
            for j in i:
                x, y = j
                r_tmp.append(lst[x][y])
            rst.append(r_tmp)
        t_rst.append(rst)

# 모든 체스판에 대한 색칠 요망 칸 수를 cnt_lst 리스트에 추가하고 최소 값을 출력
cnt_lst = []
for i in t_rst:
    cnt_lst.append(chk(i))

print(min(cnt_lst))

 

선언된 chk 함수에서 조건문을 사용해서는 안됨.

위 코드에서는 잘라내어진 각 체스판의 x, y의 위치가 좌측 상단(0, 0)인 칸의 색을 기준으로 잡고,

해당하는 reference B, reference W 중 하나만 비교 했었다.

8×8로 잘라내는 모든 경우와

검은색과 흰색을 칠하는 모든 경우를 고려해야 하는데

후자를 간과한 것이다.

---

제출 코드

# chk함수를 B_chk, W_chk함수로 수정 후 제출(결과: 맞았습니다!)

# 8×8 크기로 잘나내기 함수
def sel(x, y):
    x_lst = []
    for i in range(x, x+8):
        y_lst = []
        for j in range(y, y+8):
            y_lst.append([i, j])
        x_lst.append(y_lst)
    return x_lst

# refrence B, W 리스트 생성 함수
def ref(tmp):
    lst = []
    
    def fst_B():
        lst = []
        for i in range(8):
            if i % 2 == 0:
                lst.append('B')
            else:
                lst.append('W')
        return lst

    def fst_W():
        lst = []
        for i in range(8):
            if i % 2 == 0:
                lst.append('W')
            else:
                lst.append('B')
        return lst
    
    if tmp == 'B':
        lst.append(fst_B())
        lst.append(fst_W())
        lst.append(fst_B())
        lst.append(fst_W())
        lst.append(fst_B())
        lst.append(fst_W())
        lst.append(fst_B())
        lst.append(fst_W())
    else:
        lst.append(fst_W())
        lst.append(fst_B())
        lst.append(fst_W())
        lst.append(fst_B())
        lst.append(fst_W())
        lst.append(fst_B())
        lst.append(fst_W())
        lst.append(fst_B())
    
    return(lst)

# 각 리스트와 reference B와 비교 후 색칠 요망 칸 수 리턴
def B_chk(lst): # lst는 8×8 리스트
    cnt = 0
    r_lst = []
    for i in ref('B'):
        r_lst.append(i)
    for i in range(len(lst)):
        for j in range(len(lst[i])):
            if lst[i][j] != r_lst[i][j]:
                cnt += 1
    return cnt

# 각 리스트와 reference W와 비교 후 색칠 요망 칸 수 리턴
def W_chk(lst): # lst는 8×8 리스트
    cnt = 0
    r_lst = []
    for i in ref('W'):
        r_lst.append(i)
    for i in range(len(lst)):
        for j in range(len(lst[i])):
            if lst[i][j] != r_lst[i][j]:
                cnt += 1
    return cnt

# M×N 크기의 보드 input
N, M = map(int, input().split())
NM = []
for i in range(N):
    NM.append(input())

# 문자열을 리스트로 변환
lst = []
for i in NM:
    c = []
    for j in i:
        c.append(j)
    lst.append(c)

# 모든 경우의 8×8 리스트 생성
t_rst = []
for row in range(len(NM)-7):
    for col in range(len(NM[0])-7):
        rst = []
        tmp = sel(row, col)
        for i in tmp:
            r_tmp = []
            for j in i:
                x, y = j
                r_tmp.append(lst[x][y])
            rst.append(r_tmp)
        t_rst.append(rst)

# 모든 체스판에 대한 색칠 요망 칸 수를 cnt_lst 리스트에 추가하고 최소 값을 출력
cnt_lst = []
for i in t_rst:
    cnt_lst.append(B_chk(i))
    cnt_lst.append(W_chk(i))

print(min(cnt_lst))

 

8×8로 잘라낸 체스판을 reference 리스트와 비교하는 chk 함수에서 조건문을 제거하고,

왼쪽 상단 칸이 검은색으로 시작하는 경우를 확인하는 B_chk와,

흰색으로 시작하는 경우를 확인하는 W_chk함수로 분리하였다.

왼쪽 상단 칸이 검은색으로 시작하는 경우와 흰색으로 시작하는 경우 모두를 확인하기 위함이다.

---

해결한 방법

꽤 고전했던 문제였다.

작은 문제들로 쪼개어 하나 하나 해결하는 방법을 고민 했다.

그러다보니 함수를 많이 만들어 쓰게 되었고,

결국 아래의 1~5번의 순서로 문제를 해결할 수 있었다.

 

1. 8×8 크기로 잘라내기 → 함수 sel (select) 생성
2. 잘라낸 체스판과 비교할 refrecnce 생성  →  함수 ref (reference) 생성
3. 잘라낸 체스판을 refrence와 비교하기  →  함수 B_chk, W_chk (Black check, White check) 생성
4. 잘라낸 모든 체스판에 대하여 1, 2, 3 반복하기
5. 3에서 가장 적게 카운트된 체스판의 칸 수를 출력하기 

 

제일 먼저 예제 입력 중 하나(예제 입력 2)를 선택하고,

x, y 주소값을 표기하여 시각화하였다.

2차원 리스트 사용시 한눈에 보기 좋도록 하기 위함이다.

M = [
#0123456789012  y/x
'BBBBBBBBWBWBW', #0
'BBBBBBBBBWBWB', #1
'BBBBBBBBWBWBW', #2
'BBBBBBBBBWBWB', #3
'BBBBBBBBWBWBW', #4
'BBBBBBBBBWBWB', #5
'BBBBBBBBWBWBW', #6
'BBBBBBBBBWBWB', #7
'WWWWWWWWWWBWB', #8
'WWWWWWWWWWBWB'] #9

 

reference 리스트와 비교 시 주소 확인을 용이하게 하기 위해 문자열을 리스트로 변환 했다.

# 문자열을 리스트로 변환
lst = []
for i in NM:
    c = []
    for j in i:
        c.append(j)
    lst.append(c)

 

예제의 M×N 크기의 보드에서 모든 경우의 8×8 크기의 체스판을 잘라내어 리스트에 넣는 코드를 작성했다.

이때 8×8 크기의 체스판을 잘라내기 위해

앞서 만들었던 sel함수를 적용하였다.

# 모든 경우의 8×8 리스트 생성
t_rst = []
for row in range(len(NM)-7):
    for col in range(len(NM[0])-7):
        rst = []
        tmp = sel(row, col) # 8×8크기로 잘라내는 sel함수
        for i in tmp:
            r_tmp = []
            for j in i:
                x, y = j
                r_tmp.append(lst[x][y])
            rst.append(r_tmp)
        t_rst.append(rst)

 

8×8 크기로 잘라낸 모든 경우의 체스판을 B_chk, W_chk 함수로 reference와 비교해

모든 경우의 색칠 요망 칸 수를 cnt_lst 리스트 에 모으고,

cnt_lst 리스트의 값 중 최소값을 출력하였다.

# 모든 체스판에 대한 색칠 요망 칸 수를 cnt_lst 리스트에 추가하고 최소 값을 출력
# B_chk, W_chk 함수는 내부적으로 reference를 생성하는 ref 함수를 호출함
cnt_lst = []
for i in t_rst:
    cnt_lst.append(B_chk(i)) # B_chk 함수 호출
    cnt_lst.append(W_chk(i)) # W_chk 함수 호출

print(min(cnt_lst))