백준 1018 체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

자세한 건 위에 들어가서문제 확인하자.

 

풀이:

n, m = int(input())

board = []
error = []

for _ in range(n):
    borad.append(input())

for a in range(n-7):
    for i in range(m-7):
        idx1 = 0  # 시작이 w
        idx2 = 0  # 시작이 b
        for b in range(a,a+7):
            for j in range(i,i+7):
                if (b+j) % 2 == 0 :   #시작점이랑 같은 색이여야한다.
                    if board[b][j] != 'W' : idx1 += 1
                    if board[b][j] != 'B' : idx2 += 1
                else:                # 시작점이랑 다른색이여야한다.
                    if board[b][j] != 'B' : idx1 += 1
                    if board[b][j] != 'W' : idx2 += 1
        error.append(idx1)
        error.append(idx2)
print(min(error))

입출력 부분은 생략하겠다.

 

핵심으로 들어가서 약간 CNN 에 stride처럼 생각하며 풀어야한다.

모든 8X8 이 부분을 찾아가면서 몇개가 정답과 다른지를 기록해야한다.

 

그 아이디어로 시작점을 기준을 잡아서 계산하면된다.

 

자세히 설명을 시작하면 

for a in range(n-7):
    for i in range(m-7):
        idx1 = 0  # 시작이 w
        idx2 = 0  # 시작이 b

이 부분을 보면 n = 10 이라고 치면 우리가 봐야할 경우의 수는 0~7, 1~8, 2~9, 3~10 이렇게 4가지이다. 

따라서 우리는 가로로  n-7개를 보겠다. 세로로 n-7 개를 보면서 8X8 을 계속 훝겠다는거다.

그렇게 w로 시작할때의 오류값 idx1 , b로 시작할때 오류값 idx2 로 설정해준다.

 

다음은

for b in range(a,a+7):
            for j in range(i,i+7):
                if (b+j) % 2 == 0 :   #시작점이랑 같은 색이여야한다.
                    if board[b][j] != 'W' : idx1 += 1
                    if board[b][j] != 'B' : idx2 += 1
                else:                # 시작점이랑 다른색이여야한다.
                    if board[b][j] != 'B' : idx1 += 1
                    if board[b][j] != 'W' : idx2 += 1

a가 0 이면 b는 0~7 이렇게 해줘야 8칸을 검토 할수 있어 range(a,a+7) 로 설정했다.

j도 똑같다.

 

여기가 제일 중요하다고 생각한다.

b+j 즉 행 과 열의 합이 짝수이면 계속 맨 처음 시작점과 값이 같아야한다. 

 

WBWB

WBWB 

 

의 경우를 보면  0+0 = W , 0+2 = W 이렇게 같아야 정상이다. 이렇게 같지않다면 수정해줘야 하기 때문에 if문을 써서 idx 값을 1씩 증가 시켜준다.

i+j가 홀수이면 처음 시작한 값과 다르기때문에 이경우도 순서를 바꿔서 입력해준다.

 

이렇게 시작을 idx1, idx2로 했을때 수정 값이 출력되는데 .

이중 작은것을 답으로 채택하면 해결된다.