1018번 체스판 다시 칠하기

문제링크 : www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

이 문제를 풀기 위한 과정

 

1. chess 판의 8*8칸의 경우를 모두 조사해야한다.

    예를 들어 9*10칸의 chess판이 주어졌을 경우,

             열은 [0,8), [1,9)  행은[0,8) 로 나눠서 모든 경우의 수를 따져봐야한다.

 

 

2. 8*8칸 내에서 수정이 필요한 칸의 수를 알아봐야 한다.

  <첫번째 접근법>

     8*8칸을 둘러볼때 이중 for문을 사용하는데 그 시작점을 다르게 한다.

     ex) 1번 시작 : (0,0) -> (0,7) -> (1,0)      2번 시작 : (0.7) -> (0,0) -> (1,7) 

     3번 시작 : (7,0) -> (7,7) -> (6,7)      4번 시작 : (7,7) -> (7,0) -> (6,7)

=> 조건을 구분하는 자체가 복잡하고 같은 코드가 반복되어 길어지게 됨

 

<두번째 접근법>

시작 지점의 좌표의 합이 홀수인지 짝수인지 고려.

->시작지점 좌표의 값이 "B"인지 "W"인지 확인

-> if 시작지점 홀, B이었다면, 짝수칸이 W인지 확인

-> 틀린 칸이 수 세기

=> 코드 자체가 복잡하진 않으나 시작지점을 고쳐야 더 적은 수가 나오는 경우는 고려하지 않음

 

<최종 접근법>

(해당 좌표의 x+y값) 짝수칸이 W일 경우 고쳐야하는 칸의 수 changeCountW

(해당 좌표의 x+y값) 짝수칸이 B일 경우 고쳐야하는 칸의 수 changeCountB

라고 가정하고 각각의 경우 몇 칸을 고쳐야하는지 확인

-> 둘중 더 작은 changeCount를 리턴

 

def check(chess, columnR, rowR):
    changeCountW = 0
    changeCountB = 0
    for i in range(rowR,8+rowR):
        for j in range(columnR,8+columnR):
            if(((i+j)%2 == 1) & (chess[i][j]!="B")):
                changeCountW+=1
            elif(((i+j)%2 == 0) & (chess[i][j]!="W")):
                changeCountW+=1
            if (((i + j) % 2 == 1) & (chess[i][j] != "W")):
                changeCountB += 1
            elif (((i + j) % 2 == 0) & (chess[i][j] != "B")):
                changeCountB += 1
    if (changeCountW>changeCountB):
        return changeCountB
    return changeCountW

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

chess = list()
for i in range(0,M):
    chess.append(sys.stdin.readline())

list = list()
for i in range(0,M-7):
    for j in range(0,N-7):
        list.append(check(chess,j,i))

minimum = 64
for item in list:
    if(item<minimum):
        minimum = item

print(minimum)

 

코드 자체를 마무리 할 수 있었던 건 좋으나 처음엔 첫번째로 생각한 접근법에서 헤어나오질 못해 결국 구글링으로 짝수칸, 홀수칸을 구분해 생각해야 한다는 힌트를 얻었다. 문제에서 말하는 과정을 그대로 코드로 옮기려고 하기보다는 결과값을 빠르게 도출할 수 있는 알고리즘에 대한 고려가 필요한 듯 하다.