백준 1018번 - 체스판 다시 칠하기

알고리즘/24-25 겨울 코딩테스트 스터디

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

js-kkk 2025. 1. 22. 22:22

문제 링크

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

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 MxN 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8x8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8x8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8x8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력 조건

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력 조건

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

입력 예시1

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

출력 예시1

입력 예시2

10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

출력 예시2

입력 예시3

8 8
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB

출력 예시3

입력 예시4

9 23
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBW

출력 예시4

입력 예시5

10 10
BBBBBBBBBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBBBBBBBBB

출력 예시5

입력 예시6

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWWWB
BWBWBWBW

출력 예시6

입력 예시7

11 12
BWWBWWBWWBWW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBWWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW

출력 예시7

풀이 전 생각

우선, 다시 칠해야 하는 정사각형의 개수가 최소가 되도록 하는 8X8 을 찾고 -> 제일 왼쪽,위에 해당하는 경우가 검은색이거나 흰색인 경우, 총 2가지 경우에 따라서 8X8 에서 다시 칠해야 하는 곳을 하나씩 찾으며 count를 해준다.

순서

1.제일 왼쪽,위에 해당하는 경우가 흰색,검은색인지에 따라 잘 만들어진 체스판을 2차원 배열로 선언한다.

2.빈 배열에 위의 두 경우에 따라 입력받은 체스판에서 8X8 로 잘라 비교하며 다시 칠해야 하는 정사각형의 개수(잘 만들어진 체스판과 다른 곳의 개수)를 저장한다.

3.저장한 배열에서 가장 적은 개수를 출력한다.

이런 식으로 진행하면 모든 경우에 대해서 개수를 확인할 수 있을 것 이다.

실수한 예제 코드

#제일 왼쪽,위에 해당하는 경우가 흰색,검은색인지에 따라 잘 만들어진 체스판을 2차원 배열로 선언한다.

white_arr=['WBWBWBWB',
           'BWBWBWBW',
           'WBWBWBWB',
           'BWBWBWBW',
           'WBWBWBWB',
           'BWBWBWBW',
           'WBWBWBWB',
           'BWBWBWBW',]

black_arr=['BWBWBWBW',
           'WBWBWBWB',
           'BWBWBWBW',
           'WBWBWBWB',
           'BWBWBWBW',
           'WBWBWBWB',
           'BWBWBWBW',
           'WBWBWBWB',]

m,n = map(int,input().split())

input_arr = [input() for _ in range(m)]
diff_arr = []
#빈 배열에 위의 두 경우에 따라 입력받은 체스판에서 8X8 로 잘라 
#비교하며 다시 칠해야 하는 정사각형의 개수(잘 만들어진 체스판과 다른 곳의 개수)를 저장한다.

for i in range(m-8+1):   #8X8 배열 이므로 -8+1
    for j in range(n-8+1):
        count = 0
        for a in range(8):
            for b in range(8):
                if input_arr[i][j]=='W':
                    if input_arr[i+a][j+b]!=white_arr[a][b]:
                        count+=1
                else:
                    if input_arr[i+a][j+b]!=black_arr[a][b]:
                        count+=1
        diff_arr.append(count)

#저장한 배열에서 가장 적은 개수를 출력한다.
print(min(diff_arr))

코드를 작성하고 제출을 해보니, 분명 맞는 것 같은데 틀려서 확인을 해보니

문제를 읽을 때 해석을 잘못한 부분이 있었다.

문제 내용 중

"""

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

"""

'하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우' 이 부분에서 8X8 배열을 체크할 때 가장 왼쪽 위에 있는 인덱스에 해당하는 것이 만약 W 라면, 이 W는 수정해서는 안되는 것으로 착각했다.

즉, WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

로 변하도록 수정해야 하는 것으로 착각했다.

수정한 예제 코드

#제일 왼쪽,위에 해당하는 경우가 흰색,검은색인지에 따라 잘 만들어진 체스판을 2차원 배열로 선언한다.

white_arr=['WBWBWBWB',
           'BWBWBWBW',
           'WBWBWBWB',
           'BWBWBWBW',
           'WBWBWBWB',
           'BWBWBWBW',
           'WBWBWBWB',
           'BWBWBWBW',]

black_arr=['BWBWBWBW',
           'WBWBWBWB',
           'BWBWBWBW',
           'WBWBWBWB',
           'BWBWBWBW',
           'WBWBWBWB',
           'BWBWBWBW',
           'WBWBWBWB',]

m,n = map(int,input().split())

input_arr = [input() for _ in range(m)]
diff_arr = []
#빈 배열에 위의 두 경우에 따라 입력받은 체스판에서 8X8 로 잘라
#두 가지 경우에 따라 비교하며 다시 칠해야 하는 정사각형의 개수(잘 만들어진 체스판과 다른 곳의 개수)를 저장한다.

for i in range(m-8+1):
    for j in range(n-8+1):
        white_count = 0
        black_count = 0
        for a in range(8):
            for b in range(8):
                if input_arr[i+a][j+b]!=white_arr[a][b]:
                    white_count+=1
                if input_arr[i+a][j+b]!=black_arr[a][b]:
                    black_count+=1
        diff_arr.append(min(black_count,white_count))

#저장한 배열에서 가장 적은 개수를 출력한다.
print(min(diff_arr))

생각

풀면서 든 생각인데 사실 이렇게 white_arr,black_arr 를 각각 만들고 비교하며 진행하는 것도 가능하나, 체스판의 규칙을 생각해보면

WBWBWB , BWBWBW 이런식으로 같은 패턴이 반복되게 되는데, 2차원 배열의 각각의 인덱스를 더한 후 2로 나누었을 때 나머지가 홀수인지 짝수인지에 따라 'B' , 'W' 를 구하고 count를 하는 방법으로 진행하면 코드를 조금 줄일 수 있을 것 같다.

예를 들어,

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

라고 입력을 받으면

input_arr[0][0] 에서 (0+0)%2 는 0 이므로 짝수 -> 'W',

input_arr[0][1] 에서 (0+1)%2 는 1 이므로 홀수 -> 'B',

input_arr[0][2] 에서 (0+2)%2 는 0 이므로 짝수 -> 'W',

input_arr[1][0] 에서 (1+0)%2 는 1 이므로 홀수 -> 'B',

이런 식의 규칙이 생기는데 이를 이용해도 좋을 것 같다.

저작자표시 비영리 변경금지 (새창열림)

'알고리즘 > 24-25 겨울 코딩테스트 스터디' 카테고리의 다른 글

백준 2164번 - 카드2 - 파이썬(Python) (0)	2025.01.31
백준 4779번 - 칸토어 집합 - 파이썬(Python) (0)	2025.01.26
백준 15652번 - N과 M (4) - 파이썬(Python) (0)	2025.01.26
백준 2447번 - 별찍기-10 - 파이썬(Python) (0)	2025.01.24
24-25 겨울 코딩테스트 스터디 (1)	2025.01.22

현재글백준 1018번 - 체스판 다시 칠하기 - 파이썬(Python)

js-kkk 님의 블로그

개발블로그

이코테, 이것이 코딩테스트다, 백준 2447, 파이썬, 슬라이딩 윈도우, 백준 15652번, 백준 2559,

Today :
Yesterday :

js-kkk 님의 블로그