[백준] 1018번 : 체스판 다시 칠하기 (파이썬)

뚝딱이 공학도·2022년 3월 2일
2

문제풀이_백준

목록 보기
75/160



문제



나의 답안

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

mtr=[]
cnt=[]
for i in range(n):
    mtr.append(input())
    
for a in range(n-7):
    for b in range(m-7):#8*8로 자르기 위해, -7해준다
        w_index=0 #흰색으로 시작
        b_index=0 #검은색으로 시작
        for i in range(a,a+8):#시작지점
            for j in range(b,b+8):#시작지점
                if (i+j)%2==0:#짝수인 경우
                    if mtr[i][j]!='W':#W가 아니면, 즉 B이면
                        w_index+=1#W로 칠하는 갯수
                    else:#W일 때
                        b_index+=1#B로 칠하는 갯수
                else:#홀수인 경우
                    if mtr[i][j]!='W':#W가 아니면, 즉 B이면
                        b_index+=1#B로 칠하는 갯수
                    else:
                        w_index+=1#W로 칠하는 갯수
                        
        cnt.append(w_index) #W로 시작할 때 경우의 수
        cnt.append(b_index) #B로 시작할 때 경우의 수
print(min(cnt))

접근 방법

  • 다시 칠해야 하는 경우
    • 하나는 맨 왼쪽 위 칸이 흰색인 경우
    • 하나는 검은색인 경우
  • 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다
  • 문제 조건에 따라, 8×8 크기의 체스판으로 잘라내야 함
  • 행과 열의 인덱스의 합계가 짝수면 처음 색과 같아야, 홀수면 달라야한다.
    • 예를들어
i,ji,ji,ji,j
0,00,10,20,3
1,01,11,21,3
2,02,12,22,3
3,03,13,23,3

와 같은 배열을 이루고 있다고 하면
아래와 같이 합이 홀수인 경우는
처음과 다른 색을 이루고 있어야 서로 다른 색의 배열을 가질 수 있다.

i,ji,ji,ji,j
0 (W)1 (B)2 (W)3 (B)
1 (B)2 (W)3 (B)4 (W)
2 (W)3 (B)4 (W)5 (B)
3 (B)4 (W)5 (B)6 (W)

  1. n과 m을 입력받고, 문자열을 저장할 mtr 배열과 다시 칠해야 하는 정사각형 개수를 저장할 cnt 배열을 선언한다.

  2. 반복문으로 체스판을 색칠한다.

  3. 체스판을 8*8으로 잘라주어야 하기에

    for a in range(n-7):
        for b in range(m-7): 

    와 같이 반복문을 돌려준다.

  4. 체스판이 무슨 색으로 시작하는지 판별하기 위해 w_index와 b_index 변수를 0으로 초기화 해준다.

  5. 행과 열의 시작지점을 파악하기 위해 다음과 같은 반복문을 돌려준다.

    for i in range(a,a+8):#시작지점
                for j in range(b,b+8):#시작지점 
  6. 이후 짝수인 경우, 각 값이 W인지 아닌지에 따라 w_index와 b_index 변수를 증가시켜 준다.
    짝수인 경우(첫번째 값과 같아야 함)

    • 6-1. 해당 값이 B이면 W로 칠해야 하므로, w_index을 1증가시켜 준다.
    • 6-2. 해당 값이 W이면 B로 칠해야 하므로, b_index을 1증가시켜 준다.
  7. 마찬가지로 홀수인 경우, 각 값이 W인지 아닌지에 따라 w_index와 b_index 변수를 증가시켜 준다.
    홀수인 경우(첫번째 값과 달라야 함)

    • 7-1. 해당 값이 B이면 B로 칠해야 하므로, b_index을 1증가시켜 준다.
    • 7-2. 해당 값이 W이면 W로 칠해야 하므로, w_index을 1증가시켜 준다.
  8. 각 문자열의 시작지점에 대한 모든 반복문을 종료한 후 cnt 배열에 w_index와 b_index를 추가한다.

  9. 이후 min을 사용해 다시 칠해야 하는 정사각형의 최소 개수를 출력해준다.


이게 실버 5문제라고..? 싶었던 문제이다... 나중에 다시 풀어봐야지

0개의 댓글