Post

13. Python(체스판 다시 칠하기)

13. Python(체스판 다시 칠하기)

[toc]

체스판 다시 칠하기

문제

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

제출

코드

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

인사이트

  1. 다양한 크기의 체스판을 입력 받은 후 8x8 크기의 체스판으로 잘라낸 후 몇 개의 정사각형을 다시 칠한다
    • 기본 8x8 체스판을 만들어서 비교하는 방식으로 해야 할 것이라고 생각함
  2. 가로와 세로가 보이는 걸로 보아 2차원 리스트, 중첩 반복문을 사용해야 할 것을 생각함

  3. 최솟값을 구하라 => 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 중 작은 수가 최소 수정 횟수로 정답임