[Baekjoon]백준 25682 체스판 다시 칠하기 2(골드 4) - Python

문제설명

예제 1

예제 2

문제를 살펴보면 예전에 풀었던 체스판 칠하기의 업그레이드 버전인듯하다

그래서 이전에 풀었던 코드를 참고하여 코드를 작성해보았다

n, m = map(int, input().split())
chess = []
result = []

for _ in range(n): # 2차원 배열로 변환
    row = list(input().strip())
    chess.append(row)

for i in range(n - 7):
    for j in range(m - 7):
        count_1 = 0
        count_2 = 0

        for x in range(i, i + 8):
            for y in range(j, j + 8):
                if (x + y) % 2 == 0:  # 짝수 칸
                    if chess[x][y] != 'B':
                        count_1 += 1
                    if chess[x][y] != 'W':
                        count_2 += 1
                else:  # 홀수 칸
                    if chess[x][y] != 'W':
                        count_1 += 1
                    if chess[x][y] != 'B':
                        count_2 += 1

        result.append(count_1)
        result.append(count_2)

print(min(result))

이 코드에서 달라지는 점은 누적합 알고리즘을 사용하여 size만큼의 크기의 사각형에서 최소한의 개수를 찾아야한다

이전 문제에서 풀어보았듯이 2차원 배열에서 누적합 알고리즘을 사용하여 각 위치당 최소 개수를 찾아내야한다

간단하게만 설명을 하자면 

1 2 3 4

4 5 6 5

7 8 9 3

3 4 5 6

라는 리스트가 있을 때 (3, 3)의 누적합을 구하고자 한다면 (3,2), (2, 3)의 누적합을 합해주고,

(2,2)의 누적합이 두 번 계산되었기 때문에 이를 빼주면 해당 위치의 누적합을 구할 수 있게 된다

이러한 점을 활용하여 기존의 코드와 결합하여 작성하였다

prefix_sum = [[0] * (col + 1) for _ in range(row + 1)]

for x in range(1, row + 1):
    for y in range(1, col + 1):
        if (x + y) % 2 == 0:
            if chess[x-1][y-1] == 'B': # 변경할 필요가 없음
                prefix_sum[x][y] = prefix_sum[x-1][y] + prefix_sum[x][y-1] - prefix_sum[x-1][y-1]
            else: # 변경이 필요하므로 +1 연산 추가
                prefix_sum[x][y] = prefix_sum[x-1][y] + prefix_sum[x][y-1] - prefix_sum[x-1][y-1] + 1
        else:
            if chess[x-1][y-1] == 'W': # 변경할 필요가 없음
                prefix_sum[x][y] = prefix_sum[x-1][y] + prefix_sum[x][y-1] - prefix_sum[x-1][y-1]
            else: # 변경이 필요하므로 +1 연산 추가
                prefix_sum[x][y] = prefix_sum[x-1][y] + prefix_sum[x][y-1] - prefix_sum[x-1][y-1] + 1

누적합을 저장하기 위한 리스트를 하나 만들어주고, 이 리스트에 값을 저장해주면 된다

만약 짝수일때 B로 설정하였다면 해당 위치가 B인 경우에는 값을 그대로 두어도 되지만, W인 경우에는 

색깔을 변경해야하기 때문에 해당 위치에 +1을 더해주면 된다

 

이제 두 개의 for문을 통해 Brute force 방법으로 현재 영역의 변경 횟수를 계산하고, 값을 갱신하여준다

이 방법 또한 위에서 설명한 2차원 리스트 누적합 계산 방법과 동일하다

최솟값을 저장하는 변수에는 한 사각형의 최대 크기를 저장하여 최솟값으로 갱신가능하게끔 설정해주었다

result = size * size
for i in range(size, row + 1):
    for j in range(size, col + 1):
        # 현재 영역의 색상 변경 횟수를 계산
        tmp = prefix_sum[i][j] - prefix_sum[i-size][j] - prefix_sum[i][j-size] + prefix_sum[i-size][j-size]
        result = min(result, tmp, size*size-tmp) # 최솟값 갱신

만약 result를 너무 작게 설정해버리면 값이 제대로 바뀌지 않을 수 있기 때문에 주의하여야한다

이 모든 점들을 합쳐 코드를 작성한 후 제출하면 정답임을 확인할 수 있다

(처음에는 시간초과가 발생하여 다른 방법으로도 제출해보았으나, 다른 블로그를 참고하여도 

비슷한 로직을 사용하는 것을 보고 다시 제출하였더니 맞았습니다! 를 확인할 수 있었다 PyPy3로 제출하여도 된다)

import sys

row, col, size = map(int, input().split())
chess = []

for _ in range(row): # 현재 보드판 저장
    chess.append(list(sys.stdin.readline().strip()))
    
prefix_sum = [[0] * (col + 1) for _ in range(row + 1)]

for x in range(1, row + 1):
    for y in range(1, col + 1):
        if (x + y) % 2 == 0:
            if chess[x-1][y-1] == 'B': # 변경할 필요가 없음
                prefix_sum[x][y] = prefix_sum[x-1][y] + prefix_sum[x][y-1] - prefix_sum[x-1][y-1]
            else: # 변경이 필요하므로 +1 연산 추가
                prefix_sum[x][y] = prefix_sum[x-1][y] + prefix_sum[x][y-1] - prefix_sum[x-1][y-1] + 1
        else:
            if chess[x-1][y-1] == 'W': # 변경할 필요가 없음
                prefix_sum[x][y] = prefix_sum[x-1][y] + prefix_sum[x][y-1] - prefix_sum[x-1][y-1]
            else: # 변경이 필요하므로 +1 연산 추가
                prefix_sum[x][y] = prefix_sum[x-1][y] + prefix_sum[x][y-1] - prefix_sum[x-1][y-1] + 1
                
result = size * size
for i in range(size, row + 1):
    for j in range(size, col + 1):
        # 현재 영역의 색상 변경 횟수를 계산
        tmp = prefix_sum[i][j] - prefix_sum[i-size][j] - prefix_sum[i][j-size] + prefix_sum[i-size][j-size]
        result = min(result, tmp, size*size-tmp) # 최솟값 갱신
        
print(result)