[백준 1018번] 체스판 다시 칠하기 (파이썬)

1018번: 체스판 다시 칠하기

---

문제 요구사항

N X M 크기의 보드 판이 주어진다.

(단, N & M >= 8)

8 X 8 크기로 임의로 잘라내서, 체스판으로 만들 것이다.

이때, 체스판 규격에 맞도록 다시 그리기 (덧칠) 을 수행하고, 최소 갯수로 다시 그릴 수 있는 경우를 구하여라.

 

# 체스판 규격

체스판은 맨 왼쪽 위 칸이
White (흰색) 으로 시작

Black (검은색) 으로 시작

두가지의 경우가 있다.

---

해결 솔루션

입력받은 N X M 크기의 보드판을 8 X 8 크기로 임의의 보드판을 자르고,

규격에 따른 임의의 모든 보드판을 "체스판"으로 만들기 위한 다시 그리기 (덧칠) 갯수를 구한다.

그 중 가장 작은 수를 찾는다.

 

[솔루션 접근법]

이때 문제 조건에 의하면,

8 X 8 크기로 고정하여 보드판을 잘라내기에, 규격에 맞춘 보드판은

맨 왼쪽을 (0,0)으로 생각하고,

N X M 보드판에서, 행 좌표는의 N-7 좌표가 체스판 시작좌표 (맨 왼쪽 부분)의 마지노선 행 좌표이다.

열 좌표는 M-7 좌표가 체스판 시작좌표 (맨 왼쪽 부분)의 마지노선 열 좌표이다.

 

따라서, (0,0) 부터 (N-7, M-7) 까지 8 X 8 크기로 보드판을 만들 수 있고,

해당 구간에 속한 모든 보드판을 "체스판"으로 만들기 위해

다시 그리기 (덧칠) 갯수를 구한다.

 

# 임의의 보드판, 최소 덧칠 갯수 구하기

두가지 경우로 임의의 보드판에서 덧칠 갯수를 구하고, 두가지 경우 중 최소 덧칠 개수를 구했다.

1. 맨 왼쪽이 "W" 로 시작하는 경우

2. 맨 왼쪽이 "B"로 시작하는 경우

이 두가지 경우로 나눠서 한가지 임의의 보드판에서 덧칠 개수를 구했다.

 

덧칠 개수를 구할 때는

"체스판"에서 "B" & "W"가 순서대로 섞여서 나오는 규칙을 추론해서

보드판의 row & col 값을 토대로 row 홀수이면,

col 홀수이면,

(row, col) 좌표에 속한 색깔이 "W가 아니면, "W"가 맨 왼쪽으로 시작할 경우의 덧칠 개수변수를 하나 증가시켰다.

(row, col) 좌표에 속한 색깔이 "W이면, "B"가 맨 왼 쪽으로 시작할 경우의 덧칠 개수변수를 하나 증가시켰다.

col 짝수이면,

(row, col) 좌표에 속한 색깔이 "B가 아니면, "W"가 맨 왼쪽으로 시작할 경우의 덧칠 개수변수를 하나 증가시켰다.

(row, col) 좌표에 속한 색깔이 "B이면, "B"가 맨 왼 쪽으로 시작할 경우의 덧칠 개수변수를 하나 증가시켰다.

 

row 짝수이면,

col 홀수이면,

(row, col) 좌표에 속한 색깔이 "B가 아니면, "W"가 맨 왼쪽으로 시작할 경우의 덧칠 개수변수를 하나 증가시켰다.

(row, col) 좌표에 속한 색깔이 "B이면, "B"가 맨 왼 쪽으로 시작할 경우의 덧칠 개수변수를 하나 증가시켰다.

col 짝수이면,

(row, col) 좌표에 속한 색깔이 "W가 아니면, "W"가 맨 왼쪽으로 시작할 경우의 덧칠 개수변수를 하나 증가시켰다.

(row, col) 좌표에 속한 색깔이 "W이면, "B"가 맨 왼 쪽으로 시작할 경우의 덧칠 개수변수를 하나 증가시켰다.

 

그렇게, 구해진 맨 왼쪽 "W" 시작, 맨 왼쪽 "B" 시작 두가지 경우의 값 중 최솟값을

보드판의 최소 덧칠 갯수와 비교해 작다면, 최소 덧칠 개수를 해당 임의의 보드판 최솟값으로 값을 업데이트 시켰다.

 

정리

따라서, 솔루션에서 구조적으로 접근한 대로

N X M 크기의 보드판에서 8 X 8 크기 체스판으로 자를 수 있는 모든 임의의 보드판의

모든 좌표 값을 검사하면서 다시 그리기 (덧칠) 개수를 구했다.

그리고, 최소 그리기 개수를 최종적으로 구했다.

 

[사용 알고리즘]

해당 문제는 "브루트포스 알고리즘"으로 해결가능한 문제이다.

브루트포스 알고리즘이란, 완전탐색 & 전체탐색을 특성으로

문제 상황에 대한 모든 경우를 탐색하여 정해진 "답"을 찾는 알고리즘이라고 정의된다.

따라서, 알고리즘 구현은 비교적 쉬운편에 속하고, 실행시간이 느리다는 단점이 있다.

 

[코드 리뷰]

문제를 해결하고, 다른 사람들의 코드를 보니

8 X 8 크기로 지정한 임의의 보드판에서 다시 그리기 (덧칠) 개수를 구할 때

내가 구현한 것보다 좀 더 단순한 방법으로 구현했다는 사실을 깨달았다.

나는 8 X 8 크기의 보드판에서 "B" & "W" 색칠 규칙을 row & col 단위로 보고,

모든 row & col 경우를 고려해 좌표 위치에 따른 알맞은 색깔을 비교하는 식으로 구현했다.

 

다른 사람들은

임의의 보드판에서 특정 위치를 좌표 값으로 이해하고,

(row, col) 로 좌표 값을 이해했다.

row + col 값이 짝수이면,

(row, col) 좌표에 위치한 색깔이 "W" 가 아니면, 맨 왼쪽 위가 "W"일 때의 덧칠 개수 하나 추가했다.

맞다면, "B"일 때의 덧칠 개수 하나 추가했다.

 

row + col 값이 홀수이면,

(row, col) 좌표에 위치한 색깔이 "B" 아니면, 맨 왼쪽 위가 "W" 일 때의 덧칠 개수 하나 추가했다.

맞다면, "B"일 때의 덧칠 개수 하나 추가했다.

 

정리해서, row & col 은

결국 2차원 배열에서 각각 행 좌표 & 열 좌표로 이해되기에,

좌표 값으로 생각하여 반복적인 검사를 진행할 수 있도록 일관된 규칙을 찾아내고,

"수식화"를 진행 후, 코드로 보다 간편하게 구현했다는 사실을 깨달을 수 있었다.

---

깨달음

# 반복문

이전까지는 반복문에 대해서 회의감이 있었다.

반복문에서 사용되는 변수는 default 값이 1이 아닌 0부터 시작인걸까? 에 대해서 이전부터 의문점을 지니고 있었다.

이번 문제를 품으로써 그러한 의문점을 풀어낼 수 있었다.

프로그래밍에서 사용되는 자료구조를 효율적으로 사용해내기 위해서 0으로 설정해뒀다라고 짐작해본다.

자료구조 중, 배열이 있다.

배열은 특정한 크기로 선언하여 그 크기만큼 배열이 생성된다. 그리고, 그 배열의 가장 맨 앞의 자리는 0부터 시작한다.

즉, 많은 데이터를 배열에 삽입하여 활용할 때,

반복문에서 default 값을 0으로 시작하면, 또다른 변수 선언없이 빠르게 코드를 작성할 수 있다는 점에 반복문에서 사용되는

변수의 default 값이 0이라는 사실을 짐작할 수 있었다.

 

# 디버깅

이번 문제는 VS Code 툴을 이용해서 코드를 구현했다.

처음 코드를 작성하고, 실행을 돌려보니

예제 입력 값에 대해 출력 값이 올바르지 않게 나왔었다.

그래서, 이번 기회로 디버깅 툴을 사용해보았고, 그에 따라 디버깅 툴을 다루는 법을 익힐 수 있게 되어

이러한 경험을 기록하기 위해 이 글을 작성해본다.

 

[디버깅 구간 체크]

빨간점, 디버깅 구간

VS Code에서 코드 줄에서 바로 왼쪽을 클릭하면, 빨간점으로 표시된다.

이 빨간점은 디버깅 구간을 설정하는 것이고, 점 2개를 찍어 디버깅 구간을 설정한다.

 

디버깅 구간 설정은

시작 위치 (첫번째 빨간점), 종료 위치 (두번째 빨간점) 을 설정하게 되는데,

컴퓨터가 내가 구현한 코드 중에서 어떻게 실행되는지 알아보고 싶은 지점을 설정하면 된다.

디버깅을 할 때는 반복문 구간 혹은 조건문 구간에 설정해둔 뒤, 코드에 선언한

변수들을 실행흐름에 따라 변화하는 것을 확인한다.

디버깅 구간 설정에 따라, 디버깅 실행에 따른 변수변화 관찰

정리해서, 디버깅 툴을 이용해 쉽고 빠르게

작성한 코드의 동작을 확인할 수 있다.

잘못 작성한 코드는 디버깅을 통해 잘못 동작되는 지점을 쉽게 확인할 수 있고,

이를 토대로 코드 수정을 거쳐 문제 상황이 요구하는 대로 수정하면 된다.

 

"이슈가 생겼을 땐, 당황하지 말고 디버깅을 하고 코드 수정에 들어가자"

---

마치며

이 문제는 "브루트 포스" 알고리즘을 토대로 약간의 힌트를 얻어서 구현한 문제이다.

다음 번에는 힌트없이 오직 내 사고로만 문제를 해결해보는 연습을 할 것이다.

 

이번 경험은 처음으로 백준 "실버" 문제를 도전해보았고, 결과는 성공이었다.

아직까진, 문제를 푸는 감은 잘 익혀지지 않았지만,

문제를 푸는 내내 "자료구조" 중요성을 한층씩 느끼고 있는 중이다.

앞으로 꾸준히 백준을 풀어보며, "자료구조" 필요성을 느끼고 이에 대한 심화 학습을 통해

여러 문제를 해결할 수 있는 사람이 되도록 성장할 것이다.

---

구현 코드 (파이썬)

# N X M 보드 입력받음
n, m = map(int,input().split(" "))


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


# test
# for _ in range(n):
#     print("%d"%(_+1) + "행", end=' =')
#     for i in range(m):
#         print(arr[_][i], end='')

#     print()


# 최소 덧칠 갯수 기록변수
best_update = -1

# N X M 보드 전체검사
for N in range(n-7):
    for M in range(m-7):

        white_first = 0
        black_first = 0
        example_update = 0
        
        # 임의의 8 X 8 보드 검사
        for row in range(N, N+8, +1):
            for col in range(M, M+8, +1):
                
                # 흰 & 검 시작 2가지 상태, 검사
                if((row + 1) % 2 != 0):
                    if((col + 1) % 2 != 0):
                        if(arr[row][col] != "W"):
                            white_first += 1
                        else:
                            black_first += 1
                    else:
                        if(arr[row][col] != "B"):
                            white_first += 1
                        else:
                            black_first += 1
                else:
                    if((col + 1) % 2 != 0):
                        if(arr[row][col] != "B"):
                            white_first += 1
                        else:
                            black_first += 1
                    else:
                        if(arr[row][col] != "W"):
                            white_first += 1
                        else:
                            black_first += 1

        # 임의의 보드 검사 완료
        if (white_first > black_first):
            example_update = black_first
        else:
            example_update = white_first
                
        # 임의의 보드 최소갯수와 기록된 최소 갯수 비교
        if (best_update == -1 or best_update > example_update):
            best_update = example_update
        
        # print(best_update, end =", ")

print(best_update)