[CLASS 2]백준 1018번 - 체스판 다시 칠하기

1018번 : 체스판 다시 칠하기

 

 

다시 생각해보면 그렇게 어려운 문제도 아닌데, 엄청 오래 고민했던 것 같다. 처음에는 이런 코드를 작성했다.

 

내 코드(오답):

N,M = map(int, input().split())
board = []
for i in range(N):
    string = input().rstrip()
    arr = []
    for char in string:
        arr.append(char)
    # board에 이중 리스트로 체스판 정보 저장
    board.append(arr)

checkBoard = [[] for _ in range(len(board))]
# j : 행 , i 열에 따라서 0과 1을 부여한 이중 리스트 생성
# 1 은 왼쪽 위 모서리가 W로 시작하는 체스판을 만들기 위해 칠해야 함을 의미
for j in range(len(board)):
    for i in range(len(board[j])):
        if board[j][i] == 'B':
            checkBoard[j].append((j+i) % 2)
        else:
            checkBoard[j].append(int(not bool((j+i) % 2)))

# 가능한 모든 8 * 8 판에서의 칠하는 횟수를 더한 sumList(이중)생성
sumList = [[0 for _ in range(M-7)] for _ in range(N-7)]
for line in range(N-7):
    for column in range(M-7):
        for i in range(line,line+8):
            sumList[line][column] += sum(checkBoard[i][column:column+8])

# 가장 적게 칠할수 있는 횟수를 출력. 순서가 바뀐 case의 경우 64-최댓값으로 결정
print(min(min(min(sumList)),64-max(max(sumList))))

 

bool로의 변환도 나오고.. 별로 쓸데없는것들을 많이 사용한다. 이렇게 만들고 나서 테스트 케이스들을 입력해 봤는데, 잘 돌아가서 그냥 제출했다.

 

그런데 틀렸다. 왜 틀렸는지 아직도 모르겠다. 현재 질문을 올려놓은 상태이다. 왜 틀렸는지 아시는 분 있으면 질문 글의 댓글이나 이 글의 댓글로 좀... 부탁합니다 ㅎㅎ

 

그 뒤 저 코드를 모두 지우고 비슷한 논리로 다시 코드를 간결하게 작성하였다.

 

내 코드:

N,M = map(int, input().split())
board = [input().rstrip() for _ in range(N)]
countList = []

for startingLine in range(N-7):
    for startingCol in range(M-7):
        count = 0

        for line in range(startingLine,startingLine+8):
            for col in range(startingCol,startingCol+8):
                if (line+col) % 2 == 0:
                    if board[line][col] != 'B':
                        count += 1
                else:
                    if board[line][col] != 'W':
                        count += 1
        
        countList.append(count)

for i in range(len(countList)):
    case1 = countList[i]
    case2 = 64 - case1
    countList.append(case2)

print(min(countList))

 

훨씬더 간결해지고, 정답이다. 핵심적인 생각은, 문제에서 주어지는 입력이 최대 50 까지밖에 되지 않으므로 브루트포스법을 이용하여 풀어도 된다는 것이다.

 

그리고 케이스가 두 가지 존재하는데, 1번 케이스를 왼쪽 위가 B인 케이스로 생각한다면, 2번 케이스는 왼쪽 위가 W인 케이스이다.

 

잘 생각해 보면 어떤 line에서 1번 케이스를 만족하기 위해 바꿔야 하는 횟수가 X 라면, 2번 케이스를 만족하기 위해 바꿔야 하는 횟수는 8 - X 이다. line은 총 8개 존재하므로 64에서 바꿔야 하는 횟수를 빼 주면, 그것이 바로 다른 케이스에서 바꿔야 하는 횟수이다.

 

나는 1번 케이스를 위한 횟수를 모두 구하여 countList에 append 로 추가하고, 마지막에 for문을 이용하여 case2를 추가해 주었다.