문제

문제 이해

사실 이 문제를 예전에 마주한 적이 있다. 근데 이걸 어떻게 풀어야 할지 감이 안잡혀서 넘겼었다. 브루트포스, 그리디, DP를 조금씩 찍먹해본 입장에서 다시봐도 잘 몰랐다. 문제 풀이에 대한 강의를 듣고도 구현을 할 수는 없었다. 그만큼 아직은 경험치와 능력치가 부족한 걸 절실하게 느끼고 있다. 근데 이 문제 솔직히 체감 난이도가 실버 4가 아니긴 하다.

이 문제는 브루트포스를 사용해서 풀 수 있다. 8*8로 맵을 잘라서 확인을 해야한다. 체스판의 종류는 2가지가 있다. 왼쪽 위가 W로 시작하는 맵, 그리고 B로 시작하는 맵이 있다. 일단 이 두가지를 2차원 배열을 이용해서 만들어놓고, N에서 -8만큼, M에서 -8만큼을 제외하고 한칸씩 이동하면서 비교해야한다. N-8, M-8이면 범위를 넘어가는 일 없이 = 오류가 생기는 일 없이 정상적으로 실행되는 코드를 짤 수 있다.

그러니까 이중 반복문을 i와 j인자로 돌리는데 y축을 N-7(이건 N-8까지니까 = 반복문 end값이여서), x축을 M-7로 돌리면 8*8의 체스판을 못 자르는데 실행될리가 없어서 편하다. 그리고 안에서는 DFS/BFS처럼 y,x 좌표 값을 함수로 넘기고, 그 함수에서 두 개의 체스판과 비교해서 다른 값이 더 적은 카운트 값을 반환한다.

그 반환된 값 중에 가장 작은 값을 찾아서 출력하면 정답이다. 인덱스를 조심해야 한다. 이런 문제 풀면 인덱스 때문에 자꾸 실수한다. 조심하자.

코드

# 백준 1018번 체스판 다시 칠하기

# 체스판 두개를 비교해서 더 작은 값을 반환하는 함수
def get_min(y, x):
    cnt1 = 0 # 체스판1을 비교해서 다른 값을 카운트
    cnt2 = 0 # 체스판2를 비교해서 다른 값을 카운트

    for i in range(8):
        for j in range(8):
            if chess1[i][j] != board[y+i][x+j]:
                cnt1 += 1
            if chess2[i][j] != board[y+i][x+j]:
                cnt2 += 1

    return min(cnt1, cnt2)


# 체스판 크기 세로N, 가로로M
N, M = map(int, input().split())
board = [input() for _ in range(N)]

# 시작이 W인 체스판/ B인 체스판 두개가 있으니까 두개를 만든다
chess1 = [["" for _ in range(8)] for _ in range(8)]
chess2 = [["" for _ in range(8)] for _ in range(8)]

for i in range(8):
    for j in range(8):
        chess1[i][j] = "W" if (i+j)%2 == 0 else "B"
        chess2[i][j] = "B" if (i+j)%2 == 0 else "W"

# 8*8로 자르는 경우의 수
min_count = int(1e9) 
# DFS처럼 조건에 맞으면 좌표값을 사용자정의 함수에 넣어서 함수 호출
# 체스판을 두개를 비교해서 둘중에 더 작은 것이 반환되도록 한다
# N-7, M-7을 해주면 조건문없이/ 인덱스 에러 없이 자를 수 있는 경우만 통과하기 때문문
for i in range(N - 7):
    for j in range(M - 7):
        min_count = min(min_count, get_min(i, j))

print(min_count)

사람마다 풀이방식이 많이 다르다. 위 코드가 좀 깔끔한 편이긴 하지만 실제로 코테를 푸는 상황에서는 이렇게 깔끔하게 풀기는 힘들 것 같다. 더 연습해야지.

DFS/BFS에서 공백 구분없이 맵을 받을 때는 input().rstrip()을 사용했지만, 그냥 input()으로 받아도 되는 것 같다.

이 문제는 하나만 잘못하면 체감난이도가 극상승한다. 더 열심히 풀어보자. 최근에 DP의 배낭문제를 이해 못해서 그런지 더 열심히 해야할 것 같다.