백준 1018 - 파이썬

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

1018번: 체스판 다시 칠하기

 

문제 풀이

이번 문제는 생각을 코드로 유도하기가 어려운 문제였다. 처음에는 현재 인덱스의 값과 다음 인덱스의 값이 같다면 다르게 바꿔주고 카운트를 해주면 되겠구나 싶어 간단하게 생각했었다. 하지만 이럴 경우 올바르게 색칠하긴 하지만 최솟값을 구할 수 없었다. 그래서 각 줄마다 바꿔야 하는 최솟값을 찾아낸 후 더하면 되겠다 싶어 아래와 같은 알고리즘을 생각해 냈다.

 

1. 흰색과 검정으로 시작한 각각의 경우 색을 몇번 바꿔줘야 하는지 갯수 셈.

2. 흰색으로 시작한 경우와 검정으로 시작한 경우 중 가장 적은 값을 저장

3. 1번과 2번을 활용하여 앞에서부터 8번째 보드까지 색을 바꾼 경우와 m-8번째 보드부터 마지막 보드까지 색을 바꾼 경우 중 더 적은 값을 저장

4. 첫번째 줄의 시작이 흰색이면 두번째 줄은 검정으로 시작하도록 함

5. 1~4번까지 8번 반복하여 (0,7),(0,m-1),(n-1,0),(n-1,m-1)에서 각각 시작한 8*8 체스판에서 가장 적게 색을 바꾼 경우를 출력

 

그런데 막상 코드로 작성하려고 하니 1번부터 4번까지는 작성할 수 있지만 5번은 어떻게 해야 할지 고민하다가 너무 코드가 난잡해지는거 같아서 또 다른 방법을 고민해 봤는데 (0,0),(1,1),(2,2)...(n-1,m-1)이 모두 같다는 점에 착안하여 풀어보려 했다. 그리하여 행의 시작이 1만큼 증가하면 마지막 열이 -1 준다는 점과 열의 시작이 1 증가한 경우 마지막 행이 -1 준다는 점을 알아내어 이를 코드로 작성하고자 하였다. ex) [0][0] ~ [n-1][m-1] -> [1][0] ~ [n-1][m-2]

 

하지만 구현 능력이 부족해서인지 이 역시 코드로 나타내기는 너무 복잡했다. 결국 다른 사람들은 어떻게 풀었나 찾아보게 되었다.

 

구글링을 해 보니 이 문제의 핵심은 다음과 같다.

 

1. 흰색으로 시작한 경우와 검정으로 시작한 경우 각각 몇 번 바꿨는지 기록해야 함.

2. i+j의 합을 이용하여 시작점과 색이 같아야 할지 아닐지를 구분.

 

여기서 i는 현재 행의 위치를, j는 현재 열의 위치를 나타내는데 i+j의 합이 짝수인 경우에는 시작 색과 같아야 한다는 것이다. 여기서 i+j의 합이 짝수인 경우가 아까 말한 0,0),(1,1),(2,2)...(n-1,m-1)이 모두 같다는 점인 것이다. 결국 이것을 공식화 한 셈이다. 이를 코드로 옮기면 다음과 같다.

 

n,m = map(int, input().split())
original = []
count = []

for _ in range(n):
    original.append(input())

for a in range(n-7):
    for b in range(m-7):
        white_index = 0 # 흰색으로 시작
        black_index = 0 # 검정으로 시작
        for i in range(a,a+8):
            for j in range(b, b+8):
                if (i+j) % 2 == 0:
                    if original[i][j] != 'W':
                        white_index += 1
                    if original[i][j] != 'B':
                        black_index += 1
                else:
                    if original[i][j] != 'B':
                        white_index += 1
                    if original[i][j] != 'W':
                        black_index += 1
        count.append(min(white_index, black_index))

print(min(count))

 

white_index와 black_index가 핵심 1번을 위한 변수이고, 첫번째 조건문인 (i+j) % 2 == 0이 핵심 2번을 위한 것이다.

 

for a in range(n-7):
    for b in range(m-7):
        white_index = 0 # 흰색으로 시작
        black_index = 0 # 검정으로 시작

 

이 반복문들은 시작점을 찾기 위한 코드이다. 여기서 반복문의 범위를 n-7과 m-7인 이유는 체스판의 크기가 8*8로 정해져 있기 때문이다.

 

if (i+j) % 2 == 0:
	if original[i][j] != 'W':
		white_index += 1
	if original[i][j] != 'B':
		black_index += 1
else:
	if original[i][j] != 'B':
		white_index += 1
	if original[i][j] != 'W':
		black_index += 1

 

(i+j)의 합이 짝수인 경우,

시작 보드가 흰색일 때 현재 보드가 흰색이 아닌 경우 white_index에 1을 더해준 것이고,

반대로 시작 보드가 검정일 때는 현재 보드가 검정이 아니라면 black_index에 1을 더해주며 검정으로 바꾼 개수를 저장한 것이다.

 

(i+j)이 합이 홀수인 경우에는 짝수일 때의 반대로 해 준 것이다.

 

느낀점

이번 문제를 풀며 아쉬웠던 점은 시간 제한이 2초라는 점과 입력 값이 8부터 50까지 적었다는 점을 깊게 생각하지 않고 4중 반복문을 사용을 고려하지 않았다는 점이다. 보통의 문제들에서는 4중 반복문을 사용하면 시간 초과가 발생하기 때문에 잘 사용하지 않는다. 그렇기 때문에 이번 문제 역시 4중 반복문으로 풀 생각을 하지 않았는데, 사실 주어진 시간과 입력값을 고려해 보면 충분히 생각해 볼 수 있었다.

그나마 만족했던 점은 풀이를 유도해 나갔던 생각들이 결국 답에 근접하며 다가갔다는 점이다. 흰색으로 시작한 경우와 검정으로 시작한 경우를 각각 비교하여 가장 적은 값을 출력하려 했던 점과 현재 행과 현재 열의 합이 짝수인 경우 시작점과 같다는 점을 공식화 하지 못해 코드로 구현하는데 어려움을 느낀 것이 아쉽기는 하지만 이런 생각과 사고를 할 수 있었다는 점이 만족스럽기도 한 문제였다.