Baekjoon 문제 풀기 (1018번 : 체스판 다시 칠하기) Python

1018번 : 체스판 다시 칠하기

1. 문제읽기

---

brute force 문제

brute force 문제인 것은 눈치 챘다.
조건을 설정하는데 까지는 성공했지만, 코드로 구현하는 과정에서 감을 잡지 못했다.
완전탐색 문제는 모든 경우의 수를 다 구하는 것이기 때문에 ‘이렇게까지 코드를 짜야한다고?’ 라는 생각이 들어도 일단 실행에 옮기는 것이 중요한 것 같다.

2. 제출 코드

---

1. 경우의 수 만큼 체스판을 비교해야한다.
2. 체스판을 자른다.
3. 체스판을 비교한다.

이런 과정으로 생각했는데, 1번까지는 코드로 구현했는데, 2번과 3번에서 막혔다.
반복문을 돌리는 것보다 좋은 방법이 있을 것이라 생각하고 여러 방법을 고민하다가 결국 시간이 너무 오버했다.
결론은 반복문을 무식하게 돌리는 것이 맞았다.
왜냐? 완전탐색이니까..
그래도 4중 for문이라니…

제출도 못한 미완성 코드지만 나중의 나를 위해 기록해둬야겠다.

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

arr = [0]*m  # m 줄의 체스판 만들기
for i in range(m) :  # m 만큼 반복
    arr[i] = input()  # n 문자열로 채우기

repeat = (n-8+1)*(m-8+1)  # 경우의 수 repeat

# 8x8 체스판
start_w = ["WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW"]
start_b = ["BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB"]

count = 0
for i in range(repeat):
    for j in range(7)

3. 공부할 것

---

가장 생각하기 어려웠던 과정은 4, 5번이었다.

1. 경우의 수를 알아낸 것 까지는 좋았는데, 그냥 2중 for문을 이용하여 반복시키면 된다.
2. 체스판이 바뀌는 수를 카운트
   1) count_w : W로 시작할 때 칠해야 하는 수 카운트
   2) count_b = B로 시작할 때 칠해야 하는 수 카운트
3. 체스판 8X8로 자르기
4. 체스판의 인덱스를 k, l 이라고 했을 때 이 두 인덱스를 더해서 짝수일 때와 홀수일 때를 나눈다. 그렇게하면 체스판의 체크 무늬를 구분할 수 있다. 이부분이 이해하기 제일 어려웠다.
5. 체스판을 if문으로 나눠 각각 “W”와 “B”와 비교한 후 다르면 count 해준다.
   1) 인덱스합이 짝수일 때 W로 시작했는데 W가 아니면 count_w +1
   2) 인덱스합이 홀수일 때 W로 시작했는데 B가 아니면 count_w +1
6. 두 방법으로 나눌 수 있다.
   1) count 변수를 최대값으로 설정 후 기준 변수와 각각의 카운트 변수를 비교한 후 작은 것을 출력한다.
   2) 리스트에 각각의 카운트 변수를 넣어 준 뒤 그 리스트의 최소값을 출력한다.

아래 방법은 6번에 2)번 방법을 사용한 코드이다.

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

arr = []
for i in range(n):
    arr.append(input())
count_arr = []

for i in range(n-7):  # 1
    for j in range(m-7):
        count_w = 0  # 2
        count_b = 0
        for k in range(i, i+8):  # 3
            for l in range(j, j+8):
                if (k+l) % 2 == 0:  # 4
                    if arr[k][l] != "W":  # 5
                        count_w += 1
                    if arr[k][l] != "B":
                        count_b += 1
                else:
                    if arr[k][l] != "B":
                        count_w += 1
                    if arr[k][l] != "W":
                        count_b += 1
        count_arr.append(count_w)
        count_arr.append(count_b)
        
print(min(count_arr))