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

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

1018번: 체스판 다시 칠하기

---

 

문제풀이

1. 브루트포스 개념알기

2. 알고리즘 생각

3. 코드 작성하기

 

---

1. 브루트포스

조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법.

https://namu.wiki/w/%EB%B8%8C%EB%A3%A8%ED%8A%B8%20%ED%8F%AC%EC%8A%A4

2. 알고리즘 생각

일단 체스판은 8*8 고정된 크기이다.

M*N크기의 보드를 8*8 크기로 자를 수 있는 모든 경우를 생각한다.

arr = [list(map(str, input().split())) for _ in range(n)]

for i in range(0, m-7):
	for j in range(0, n-7):
		for k in range(0, 8):
			str = arr[j+k][0]
			a = list(str[i:i+8])

입력을 한 줄씩 n번 받고,  i는 m j는 n으로 생각해서 8개씩 받는다.

위의 코드는 한 줄에 8개씩 끊어서 볼 수 있는 코드이다.

위의 코드에서

pattern1 = "WBWBWBWB"
pattern2 = "BWBWBWBW"

와 a 를 비교하면 된다.

 

또한 체스판의 첫 시작이 W인 경우와 B인 경우 둘 다 살펴봐야 하기 때문에 두가지 경우를 따로따로 생각해야 한다.

 

3. 최종 코드 작성

#20220121
#체스판 다시 칠하기

import sys
input = sys.stdin.readline

n, m = map(int, input().split(' '))

pattern1 = "WBWBWBWB"
pattern2 = "BWBWBWBW"
answer = sys.maxsize
arr = [list(map(str, input().split())) for _ in range(n)]


for i in range(0, m-7):

    for j in range(0,n-7):

        answerStartWithBlack = 0
        answerStartWithWhite = 0
        preAnswer = sys.maxsize

        for k in range(0, 8):
            str = arr[j+k][0]
            a = list(str[i:i+8])
            b = list(pattern1)
            c = list(pattern2)
            for h in range(8):
                if k%2 == 0:
                    if a[h] != b[h]:
                        answerStartWithWhite += 1
                    if a[h] != c[h]:
                        answerStartWithBlack += 1
                else:
                    if a[h] != c[h]:
                        answerStartWithWhite += 1
                    if a[h] != b[h]:
                        answerStartWithBlack += 1

        # print("answerStartWithWhite",answerStartWithWhite)
        # print("answerStartWithBlack",answerStartWithBlack)
        preAnswer = min(answerStartWithBlack,answerStartWithWhite)
        answer = min(answer,preAnswer)


print(answer)

최종코드는 위와 같이 작성하면 된다.