💻 Computer Science/Algorithm🐇

[python] 백준 1018 : 체스판 다시 칠하기

노가다 권씨 2024. 10. 3. 17:58
728x90
반응형

입력받은 배열을 8x8씩 잘라서 '가장 체스판에 가까운' 배열을 찾는 문제이다. 일단 '잘' 입력받아서 배열로 만들어야 한다. 문자열을 입력받을때 띄어쓰기 없이 그대로 쭈루룩 입력받으므로, 각각 문자에 접근하기위해선 그들을 각 리스트의 개별 원소로 다루는게 편하다.

a,b=map(int,input().split())

list_whole=[]

for i in range(b): #b개 열만큼 반복. 행 리스트를 전체 리스트에 append
    list_whole.append(list(input()))

list(input())으로 받으면 문자열을 BWBWBW..와 같이 입력해도 개별 문자가 하나의 리스트 원소로 저장이된다. 

아래가 출력값인데 딱 의도한대로 2차원 배열로 출력이 된다. [ ]으로 묶여있는 원소들이 하나의 행을 의미한다. 이제 이 리스트에 대해 list_whole[i][j]와 같이 위치값으로 개별원소에 접근할수있다.

 

이제 이 전체배열을 8x8씩 나눠서보는 알고리즘을 생각해보자. 

 위 그림처럼, 예를들어 10x12크기의 배열을 입력받았다면 좌측상단 0,0지점부터 행방향으로 끝까지간후 열방향으로 반복하여 배열의 전 영역을 8x8크기로 검사하는 방식을 써보자.

for i in range(a-7):
    for j in range(b-7):
        for k in range(8):
            for l in range(8):

이렇게 4중 for문을 써줘야하는데 그 중 위의 2개는 '전체 배열안에서 옮겨다니는 경우', 아래 2개 for문은 해당 8x8배열 안에서 원소별로 검사할때 사용한다. 그렇기에 보면 k와 l은 범위가 상수 8이다(0~7). 위 for문에서 a,b는 입력받은 전체 배열의 행,렬값인데 -7을 한 이유는 어차피 아래 for문에서 i,j에 대해 i+7까지 검사를 하기때문이다. i,j는 8x8행렬의 시작점을 의미한다.

 

지금까지 문자열을 입력받아 접근하기쉽게 개별원소로 리스트에 저장, 이렇게 만들어진 2차원 배열을 8x8사이즈로 행->열 순서대로 검사하는것까지 구현했다. 이제 마지막으로, 검사한 8x8배열이 체스판모양을 가지기위해 고쳐야하는 케이스를 구하는 알고리즘을 짜보자.

 

이 부분이 좀 어려웠는데.. 처음에 생각한것은 요소별로 양옆, 위 아래로 검사해서 요소값이 갖다면 cnt+1을 하는 방법이었다. B 위아래로는 W가 있어야하는데 B가 있다면 +1하는 방식.. 그러나 이런식으로 하면 누락되는 테스트케이스가 많았다. 애초에 검사시 중복도 발생하고.. 쉽지않은 방법이다. 

두번째로, B로 시작하는 배열은 홀수행 짝수열, 혹은 짝수행 홀수열에는 B가 와야되므로 이 점을 써볼까했다.

이런식으로. 배열의 첫 요소와 비교하는 방식이다. 배열의 첫요소와 같은값을 가져야하는 위치의 위치값이 다르다면 +1, 다른값을 가져야하는 위치의 위치값이 같다면 +1이다. 이 방법은 나쁘지않은 접근이었다. 다만 내가 조건을 미흡하게 줘서 답이 안나왔다. 애초에 i,j,k,l로 저 위치들을 for문 조건에 표현하는게 좀 어지러웠다. 헷갈렸다.

 

위치값을 2*k+i ..이런식으로 계속 표현하는게 헷갈려서 마음이 힘들때즈음... '아니 그냥 체스판 형식을 갖는 배열이랑 비교하면 되는거아냐?' 라는 생각이 들었다. 

for c in range(4):
    filter.append(['B','W','B','W','B','W','B','W'])
    filter.append(['W','B','W','B','W','B','W','B'])

그니까 이런 '체스판' 8x8배열을 생성해서 이 배열과 입력받은 배열을 검사해서 다른 원소 갯수를 구하면 되는것이다. B로 시작하는 배열, W로 시작하는 배열 2종류밖에 없으므로.. 

 

a,b=map(int,input().split())

list_whole=[]

for i in range(a): #b개 열만큼 반복. 행 리스트를 전체 리스트에 append
    list_whole.append(list(input()))

cnt=0 #바꾸는 횟수 
list_ans=[]
filter=[]

for c in range(4):
    filter.append(['B','W','B','W','B','W','B','W'])
    filter.append(['W','B','W','B','W','B','W','B']) 

for i in range(a-7):
    for j in range(b-7):
        for k in range(8):
            for l in range(8):
                if list_whole[k+i][l+j]!=filter[k][l]:  
                    cnt+=1
                else:
                    pass
        
        list_ans.append(cnt)
        list_ans.append(64-cnt)
        cnt=0

        
print(min(list_ans))

 

최종적인 코드이다. 위에 부분은 이미 설명했고.. 전체 리스트 list_whole을 8x8로 쪼개서, 상수같은 체스판배열 filter과 비교하여 다른원소갯수를 센다. 이때 cnt와 64-cnt를 둘다 정답배열에 넣는이유는, filter배열은 B로 시작하는 체스판배열이지만, 만약 검사배열이 W로 시작한다면 체스판 배열을 가짐에도 64가 출력될수있기에.. B로 시작하는 체스판배열과 W로 시작하는 체스판 배열 둘다 검사하기 위해 64-cnt값도 구해준후 그 모든 경우중 최솟값을 출력해주면 된다.

 

 

반응형