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

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

(실버4)

 

1. 문제

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

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

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

 

2. 아이디어

1) 입력값이 50으로 작다. -> 모든 경우의 수를 탐색하는 브루트포스 알고리즘을 사용한다.

2) 체스판은 2차원 배열로 저장한다.

3) 몇개의 칸을 칠해야하는지 cnt을 구하는 함수를 만든다.

( 현재 칸이 기대하는 색이 아니면 cnt를 +1 )

4) B로 시작하는 패턴과 W로 시작하는 패턴 두가지를 비교하는 함수를 만든다.

(이 함수에서 모든 8*8영역을 비교한다)

3. 코드

#몇개의 칸을 다시 칠해야하는지 카운트를 세는 함수
#top_x,top_y는 시작좌표다.
def count_chess(board, start_color, top_x, top_y):
    cnt = 0

	#다음 열로 넘어갈때마다 start_color를 지정해주고
    #행 순회문에서 쓸 expected_color를 업데이트해줌
    for y in range(top_y,top_y+8):
        if (y-top_y) % 2 == 0:
            expected_color = start_color
        else:
            if start_color == 'B':
                expected_color ='W'
            else:
                expected_color = 'B'
                
        #가로 방향으로 'B'와 'W'가 번갈아 나오는지 확인함.
        for x in range(top_x,top_x+8):
            if board[y][x] != expected_color:
                cnt+=1  #expected_color가 아니면 카운트 증가

            #다음칸 예상 색상 변경
            #가로 방향으로 순회할때는 한칸한칸 다 예상 색상을 매번 변경해줘야됨.
            if expected_color == 'B':
                expected_color = 'W'
            else:
                expected_color = 'B'
                
    return cnt

def find_min(board):
    min_changes = float('inf') #매우 큰값(무한대)으로 초기화해야 최솟값 찾을 수 있음.
   
   #x,y는 체스판 시작좌표
   #시작좌표에서 오른쪽, 아래로 8*8 체스판이 있어야함.
   #그래서 for문 범위를 m-7, n-7로 하는 것
   #왜냐하면, m과 n이 각각 8이라면 시작좌표 (1,1)만 찾으면 됨.
    for y in range(m-7):
        for x in range(n-7):
            #board[0][0]이 'B'로 시작하는 패턴과 'W'로 시작하는 패턴 비교
            #위에서 만든 count_chess함수 활용
            cnt1 = count_chess(board,'B',x,y)
            cnt2 = count_chess(board,'W',x,y)
            #두 경우 중 최소값 비교
            min_changes = min(min_changes, cnt1, cnt2)

    return min_changes

#본격적으로 입력받음
m,n = map(int,input().split()) 
#체스판 크기 m*n m은 세로열 갯수, n은 가로행 갯수
#근데 입력이 N M이라 뭐가 행이고 열인지 좀 헷갈렸음;;

board = []

#세로열만큼 반복해줘야됨.
#그리고 한 줄씩 리스트로 변환해서 board에 추가해줌 
for _ in range(m):
    line = input()
    board.append(list(line)) 

#함수 2개를 만들어놔서 find_min함수만 써도 최솟값을 찾을 수 있음.
print(find_min(board))

 

4. 중요한 포인트

✔️ M, N 입력값이 50이하라서 모든 경우의 수를 고려할 수 있는 브루트포스 알고리즘을 사용했다.

✔️ 필요한 값들을 return하는 함수를 만드니까 코드가 간결해지고 가독성이 좋아졌다!

필요한 값을 추려보면

-> 바꿔야할 칸의 갯수(cnt) ,

-> 비교가능한 시작좌표에서 8*8을 순회하고 board[0][0] 칸 색에 따른 cnt 최솟값

✔️ 메인 함수에는 어떤 로직이 담겨야하는지 고민하고 메인함수에서 어떤 보조함수를 이용할지 결정하는게 중요하다.

 

5. 느낀점

복잡해보이는 것도 하나씩 차근차근 풀면 풀린다!

한 문제 안에 여러개의 브론즈 문제가 있다고 생각하면 문제가 쉬워진다.

그래서 어떻게 풀어나갈지 쪼개서 적어나가다 보면 필요한 변수와 for문과 if문을 어떻게 쓸지 결정할 수 있다.

파이썬은 간단한 문법으로 내 생각을 표현할 수 있는 좋은 언어다. 파이썬 너무 좋다