[백준/Python] 체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

이 문제는 브루트포스 문제로 모든 경우의 수를 탐색해보면 되는 문제였다. 정말 하나씩 다 확인해보는 방법을 선택했다. 시작하는 글자가 'W' 일 때 0번째줄부터 시작한다고 할 때 짝수줄은  'WBWBWB...' 이고, 홀수줄은 'BWBWBW...' 으로 되니까 인덱스로 하나씩 확인해서 제대로 체스판이 칠해져있는지 확인하려고 했다. 행(i)과 열(j) 인덱스를 살펴보면 규칙을 찾을 수 있었다.

 

체스판이 'W' 부터 시작하는 경우 i와 j가 둘 다 짝수거나 홀수이면 'W'가 들어갈 자리이고, i와 j가 하나는 짝수, 하나는 홀수이면 'B'가 들어갈 자리이다.

 

(0,0)	(0,1)	(0,2)	(0,3)
(1,0)	(1,1)	(1,2)	(1,3)
(2,0)	(2,1)	(2,2)	(2,3)
(3,0)	(3,1)	(3,2)	(3,3)

 

체스판이 'B' 부터 시작하는 경우 i와 j가 둘 다 짝수거나 홀수이면 'B'가 들어갈 자리이고, i와 j가 하나는 짝수, 하나는 홀수이면 'W'가 들어갈 자리이다.

 

(0,0)	(0,1)	(0,2)	(0,3)
(1,0)	(1,1)	(1,2)	(1,3)
(2,0)	(2,1)	(2,2)	(2,3)
(3,0)	(3,1)	(3,2)	(3,3)

 

n, m = map(int, input().split()) # n = 행 개수, m = 열 개수
chess = [] # 체스판 정보 리스트
paint = [] # 다시 칠해야할 개수 저장할 리스트

# 체스판 정보 입력받기
for _ in range(n):
	chess.append(input())
	
# 전체 탐색 수행
for a in range(n-7): # 8 * 8 크기의 체스판을 옮겨가는 반복문
	for b in range(m-7):
		start_w = 0 # 'W' 로 시작할 경우 칠해야 할 개수
		start_b = 0 # 'B' 로 시작할 경우 칠해야 할 개수

        # 8 * 8 크기의 체스판 안에서 칠해야할 개수 세기 - 두 경우 모두 한번에 계산
		for i in range(a, a+8):
			for j in range(b, b+8):
				if i % 2 == 0 and j % 2 == 0: # i와 j가 모두 짝수인 경우
					if chess[i][j] != 'W': start_w += 1
					if chess[i][j] != 'B': start_b += 1
				elif i % 2 == 1 and j % 2 == 1: # i와 j가 모두 홀수인 경우
					if chess[i][j] != 'W': start_w += 1
					if chess[i][j] != 'B': start_b += 1
				else: # i와 j가 하나는 짝수, 하나는 홀수인 경우
					if chess[i][j] != 'B': start_w += 1
					if chess[i][j] != 'W': start_b += 1

		paint.append(start_w)	
		paint.append(start_b)

print(min(paint)) # 칠해야할 최소 개수 출력

1. 체스판 정보를 입력받는다.

2. 전체 탐색을 수행한다. 

    2-1. 체스판 크기를 8 * 8 로 잘라야 하므로 모든 경우의 수를 계산할 수 있도록 반복문을 통해 체스판을 옮겨다닌다.

    2-2. 8 * 8 크기로 자른 체스판 안에서 칠해야할 개수를 센다. 'W' 로 시작할 경우와 'B'로 시작할 경우 모두 한 번에 계산한다

    2-3. i와 j가 둘 다 짝수인 경우, 둘 다 홀수인 경우, 하나는 짝수 하나는 홀수인 경우로 나누어 칠해야할 개수를 센다.

    2-4. 칠해야할 개수를 리스트에 저장한다.

3. 칠해야 할 최소 개수를 출력한다.

 

그리고 변수 하나로 시간 초과가 런타임 에러가 날 수 있으니!! 변수를 제대로 맞게 쓴건지 잘 확인해야 한다! 나는 입력받을 때 for _ in range(n) 에서 n이 아닌 m으로 써서 런타임 에러가 났다.. 찾기 매우 힘들었다

 

 

---

다른 사람의 코드를 확인해보았더니 간단하게 한 줄로 들어갈 자리를 판단할 수 있었다!

 

행(i)과 열(j) 인덱스의 합을 2로 나눈 나머지가 0 이면 짝수이고, 1이면 홀수가 된다. -> (i+j) % 2 = 0 or 1

체스판이 'W' 부터 시작하는 경우 (i+j) % 2 = 0 이면 'W' 가 들어갈 자리고, (i+j) % 2 = 1 이면 'B' 가 들어갈 자리다.

체스판이 'B' 부터 시작하는 경우 (i+j) % 2 = 0 이면 'B' 가 들어갈 자리고, (i+j) % 2 = 1 이면 'W' 가 들어갈 자리다.

이것만 안다면 문제를 쉽게 해결할 수 있었다!

 

(0,0) - 0(짝수)	(0,1) - 1(홀수)	(0,2) - 0(짝수)	(0,3) - 1(홀수)
(1,0) - 1(홀수)	(1,1) - 0(짝수)	(1,2) - 1(홀수)	(1,3) -0(짝수)
(2,0) - 0(짝수)	(2,1) - 1(홀수)	(2,2) - 0(짝수)	(2,3) - 1(홀수)
(3,0) - 1(홀수)	(3,1) - 0(짝수)	(3,2) - 1(홀수)	(3,3) - 0(짝수)

 

n, m = map(int, input().split()) # n = 행 개수, m = 열 개수
chess = [] # 체스판 정보 리스트
paint = [] # 다시 칠해야할 개수 저장할 리스트

# 체스판 정보 입력받기
for _ in range(n):
	chess.append(input())
	
# 전체 탐색 수행
for a in range(n-7): # 8 * 8 크기의 체스판을 옮겨가는 반복문
	for b in range(m-7):
		start_w = 0 # 'W' 로 시작할 경우 칠해야 할 개수
		start_b = 0 # 'B' 로 시작할 경우 칠해야 할 개수

        # 8 * 8 크기의 체스판 안에서 칠해야할 개수 세기 - 두 경우 모두 한번에 계산
		for i in range(a, a+8):
			for j in range(b, b+8):
				if (i+j) % 2 == 0: # 짝수일 경우
					if chess[i][j] != 'W': start_w += 1
					if chess[i][j] != 'B': start_b += 1
				else: # 홀수일 경우
					if chess[i][j] != 'B': start_w += 1
					if chess[i][j] != 'W': start_b += 1

		paint.append(start_w)	
		paint.append(start_b)

print(min(paint)) # 칠해야할 최소 개수 출력