13. Python(체스판 다시 칠하기)
13. Python(체스판 다시 칠하기)
[toc]
체스판 다시 칠하기
문제
제출
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
m, n = map(int, input().split())
chess_list = [input() for _ in range(m)]
pattern_b = [
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB"
]
pattern_w = [
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW"
]
min_paint = float('inf')
for i in range(m - 7):
for j in range(n - 7):
count_b = 0
count_w = 0
for x in range(8):
for y in range(8):
if chess_list[i + x][j + y] != pattern_b[x][y]:
count_b += 1
if chess_list[i + x][j + y] != pattern_w[x][y]:
count_w += 1
min_paint = min(min_paint, count_b, count_w)
print(min_paint)
1
2
3
4
5
6
7
8
9
10
# 입력
8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
1
2
# 출력
1
인사이트
- 다양한 크기의 체스판을 입력 받은 후 8x8 크기의 체스판으로 잘라낸 후 몇 개의 정사각형을 다시 칠한다
- 기본 8x8 체스판을 만들어서 비교하는 방식으로 해야 할 것이라고 생각함
가로와 세로가 보이는 걸로 보아 2차원 리스트, 중첩 반복문을 사용해야 할 것을 생각함
최솟값을 구하라
=>float('inf')
를 연상함
조건
다시 칠해야 하는 정사각형의 최소 개수
를 구하는 프로그램
풀이
1. 입력값
- m, n(체스판의 크기)를 입력하고 그에 맞는 ‘B’ 혹은 ‘W’ 또한 같이 입력
2. 비교군 제작
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
pattern_b = [
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB"
]
pattern_w = [
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW"
]
- 입력된 체스판이 ‘B’와 ‘W’ 중 어떤 걸로 시작할지 몰라서 두 개를 만듦
3. 판별 과정
1) 8x8 체스판 시작 위치 탐색
1
2
3
4
for i in range(m - 8 + 1):
for j in range(n - 8 + 1):
count_b = 0
count_w = 0
i와 j는 각각 8x8 체스판의 시작 위치
for i in range(m - 8 + 1)와 for j in range(n - 8 + 1)은 모든 가능한 8x8 영역의 시작 위치를 구하기 위한 범위
m - 8 + 1과 n - 8 + 1로 범위를 지정해 m x n 보드의 끝까지 8x8 영역을 포함할 수 있도록 함
2) 두 패턴의 비교
1
2
3
4
5
6
7
for x in range(8):
for y in range(8):
if chess_list[i + x][j + y] != pattern_b[x][y]:
count_b += 1
if chess_list[i + x][j + y] != pattern_w[x][y]:
count_w += 1
min_paint = min(min_paint, count_b, count_w)
- 두 중첩 반복문인 for x in range(8)와 for y in range(8)은 현재 8x8 영역의 각 칸을 순회하여, 미리 정의된 두 가지 체스판 패턴 (pattern_b와 pattern_w)과 비교함
if chess_list[i + x][j + y] != pattern_b[x][y]: count_b += 1
는 B로 시작하는 패턴과 다를 경우 count_b를 증가시킴if chess_list[i + x][j + y] != pattern_w[x][y]: count_w += 1
는 W로 시작하는 패턴과 다를 경우 count_w를 증가시킴
3) 최솟값 출력
1
min_paint = min(min_paint, count_b, count_w)
- count_b와 count_w 중 작은 수가 최소 수정 횟수로 정답임