문제 1018. 체스판 다시 칠하기
1. 나의 코드와 발상 과정
n, m = map(int, input().split())
board_list = []
for i in range(n):
board_list.append(input())
# 연산(보드판을 일부 잘라 체크무늬로 칠해져 있는지 확인)
test_list = []
for i in range(n - 7): # 찾을 출발점
for j in range(m - 7):
first_W = 0
first_B = 0
for k in range(i, i + 8):
for l in range(j, j + 8):
if (k + l) % 2 == 0:
if board_list[k][l] != 'W':
first_W += 1
if board_list[k][l] != 'B':
first_B += 1
else:
if board_list[k][l] != 'B':
first_W += 1
if board_list[k][l] != 'W':
first_B += 1
test_list.append(min(first_W, first_B))
print(min(test_list))이번 문제는 상당히 어려웠다.
입력 부분만을 생각할 수 있었고 그 밑의 연산 라인들은 수입해온 것이다.
따라서 다시 공부해보고자 정말 오답노트다운 오답노트를 작성해볼 것이다.
연산 라인에서 내가 생각을 아예 못한 것은 아니다.
W 또는 B로 시작하는 문자열 라인을 기준으로 어떤 식을 작성해야겠다는 것은 알겠지만,
어떤 기준으로, 어떤 방식으로 구현해낼 지가 도저히 생각나지 않았다.
브루트포스 알고리즘이기 때문에 모든 경우의 수를 검토해야 하는데,
대체 8 * 8을 기준으로 입력된 라인들을 어떻게 잘라서, 어떤 조건문을 써서 접근해야 하는지에 대해
구글 선생님께 여쭤보았다.
답은 그렇게 어렵지는 않았다.
주어진 라인들을 바탕으로 해서
8 * 8씩 잘라서 모든 경우의 수를 검토해보면 되는 것이다.
(1) 입력 라인
# 입력
n, m = map(int, input().split())
board_list = []
for i in range(n):
board_list.append(input())입력 라인은 위와 같다.
다만, 문자열 안에서 하나의 문자만 확인하면 되고, 파이썬은 문자열의 인덱스로 그 자리에 있는 문자를 추출할 수 있기 때문에 이차원 배열을 만들지 않았다.
(2) 연산 라인
test_list = []
for i in range(n - 7): # 찾을 출발점
for j in range(m - 7):
first_W = 0
first_B = 0
for k in range(i, i + 8):
for l in range(j, j + 8):
if (k + l) % 2 == 0:
if board_list[k][l] != 'W':
first_W += 1
if board_list[k][l] != 'B':
first_B += 1
else:
if board_list[k][l] != 'B':
first_W += 1
if board_list[k][l] != 'W':
first_B += 1
test_list.append(min(first_W, first_B))구현하지 못한 라인이다.
답을 봐도 왜 반복문을 n - 7부터 시작하는지에 대해 의문이었다.
힌트는 체스판을 칠하는 경우의 수가 [a) 하얀색으로 시작하는 체스판 ,b) 검은색으로 시작하는 체스판] 두 가지라는 것이다.
(아래는 나의 이해과정)
Q. 그러면 어떤 기준으로 8 * 8로 잘라 원소의 개수를 판단할 것인가?
A. 조건이 틀리지 않으려면 전체 경우의 수를 모두 비교해보아야 한다. 모든 경우의 수로 잘라 보고 테스트 케이스마다의 다시 색칠해야 하는 횟수를 저장하여 비교해주어야 한다.
Q. 그렇다면 8 * 8은 어떻게 자를 것인가?
A. 이 경우 for문을 중첩하여 사용하면 된다.
예시)
다음과 같은 입력 예시가 주어진다고 하자 (n = 10, m = 10)
| B | W | B | W | B | W | B | W | B | W |
| B | W | B | W | B | W | B | W | B | W |
| B | W | B | W | B | W | B | W | B | W |
| W | B | W | B | W | B | W | B | W | B |
| W | B | W | B | W | B | W | B | W | B |
| W | B | W | B | W | B | B | B | B | B |
| B | B | B | B | B | B | B | B | B | B |
| B | B | B | B | B | B | B | B | B | B |
| B | W | W | W | W | W | W | W | W | W |
| W | W | W | B | B | B | B | B | B | B |
1) 첫번째 반복 때 보아야 할 문자열
| B | W | B | W | B | W | B | W | B | W |
| B | W | B | W | B | W | B | W | B | W |
| B | W | B | W | B | W | B | W | B | W |
| W | B | W | B | W | B | W | B | W | B |
| W | B | W | B | W | B | W | B | W | B |
| W | B | W | B | W | B | B | B | B | B |
| B | B | B | B | B | B | B | B | B | B |
| B | B | B | B | B | B | B | B | B | B |
| B | W | W | W | W | W | W | W | W | W |
| W | W | W | B | B | B | B | B | B | B |
2) 두번째 반복 때 보아야 할 문자열
| B | W | B | W | B | W | B | W | B | W |
| B | W | B | W | B | W | B | W | B | W |
| B | W | B | W | B | W | B | W | B | W |
| W | B | W | B | W | B | W | B | W | B |
| W | B | W | B | W | B | W | B | W | B |
| W | B | W | B | W | B | B | B | B | B |
| B | B | B | B | B | B | B | B | B | B |
| B | B | B | B | B | B | B | B | B | B |
| B | W | W | W | W | W | W | W | W | W |
| W | W | W | B | B | B | B | B | B | B |
3) 세번째 반복 때 보아야 할 문자열
| B | W | B | W | B | W | B | W | B | W |
| B | W | B | W | B | W | B | W | B | W |
| B | W | B | W | B | W | B | W | B | W |
| W | B | W | B | W | B | W | B | W | B |
| W | B | W | B | W | B | W | B | W | B |
| W | B | W | B | W | B | B | B | B | B |
| B | B | B | B | B | B | B | B | B | B |
| B | B | B | B | B | B | B | B | B | B |
| B | W | W | W | W | W | W | W | W | W |
| W | W | W | B | B | B | B | B | B | B |
이렇게 보려면 board_list의 [i][j]부터 시작해서 [i+7][j+7]번째까지 확인하는 로직을 갖추어주면 된다.
그 코드는 다음과 같다.
## 입력받은 예시에서 테스트 할 문자열 만을 반복 연산하는 코드
test_list = []
for i in range(n - 7): # 찾을 출발점
for j in range(m - 7):
first_W = 0
first_B = 0
for k in range(i, i + 8):
for l in range(j, j + 8):i, j의 range가 n-7, m-7인 이유는 시작점이 인덱스 0부터 시작하기 때문이다.
위의 예시 중 3)의 예시처럼만 가면 되기 때문에 n - 7을 해준다. (안 해주면 out of range가 생긴다.)
그다음 for l in range(j, j + 8): 라인 아래에서 조건문을 돌려준다.
## W 또는 B가 먼저 시작하는 보드판으로 바꾸기 위해 색칠해야 하는 정사각형 개수를 세는 조건문
if (k + l) % 2 == 0:
if board_list[k][l] != 'W':
first_W += 1
if board_list[k][l] != 'B':
first_B += 1
else:
if board_list[k][l] != 'B':
first_W += 1
if board_list[k][l] != 'W':
first_B += 1
test_list.append(min(first_W, first_B))이게 제일 어려웠다.
W로 시작하는 때에는 어떻게 세고, B로 시작하는 때에는 어떻게 세고 하는 것이 생각하기 어려웠는데,
그렇게 하는 것이 아니라, 4중 for문으로 불러온 그 자리의 문자열을 기준으로
처음이 W일 때 바꿔야 하는 횟수, B일 때 바꿔야 하는 횟수를 각각 세주면 된다. 이를 first_W, first_B 변수 안에 담아준다.
쉽게 말해
k, l은 불러온 8 * 8의 문자열에서 2차원 배열의 자리값과 같다.
board_list[k][l]가 board_list [0][0] 일 때,
WBWB... 를 갖추기 위해서는 W가 나와야 할 것이고, 만약 이때 B가 나온다면, first_W를 1씩 더해주어야 한다.
반대로 BWBW.... 를 갖추기 위해서는 B가 나와야 할 것이고, 만약 이때 W가 나온다면, first_B를 1씩 더해주어야 한다.
그런 다음 test_list에 min(first_W, first_B)를 해서 더 적게 나오는 수만 test list에 넣어준다.
(3) 출력
print(min(test_list))test_list 중 가장 작은 값이 본 문제의 답이다.
print를 해준다.
2. 아쉬운 점
구현하는 실력이 그렇게 좋지 못하다는 것을 느꼈다.
실버 5 문제 마지막을 이 친구와 해서 다행이다.
4중 for문을 쓸 수도 있다는 것을 깊이 새겨본다.
문제출처
'Problem Solving' 카테고리의 다른 글
| [백준] 1181 단어 정렬 python 알고리즘 문제 (0) | 2022.04.24 |
|---|---|
| [백준] 10814 나이순 정렬 python 알고리즘 (0) | 2022.04.24 |
| [백준] 7568 덩치 python 알고리즘 문제 (0) | 2022.04.20 |
| [백준] 11650 좌표 정렬하기 python 알고리즘 문제 (0) | 2022.04.20 |
| [백준] 10989 수 정렬하기 python 알고리즘 문제 (0) | 2022.04.20 |
댓글