오늘의 문제
https://www.acmicpc.net/problem/1018
모든 경우의 수를 탐색함으로서 원하는 답을 찾는 브루트 포스 알고리즘을 이용해야 풀리는 문제다.
포인트 쳌쳌
- 최초 input되는 면적은
8 * 8이상50 * 50이하의 직사각형이다. - input으로 주어진 면적 중
8 * 8사이즈의 임의의 정사각형을 탐색해야 한다. 즉, 찾을 수 있는 모든8 * 8면적에 대한 탐색 결과, 바꿔야 할 색깔의 count 수가 최소일 때 그 count 값이 정답이 된다. - 모든 행과 열을 탐색하기 위해 List(배열)와 이중 for문(2차원 배열)을 사용했다.
- 색을 변경할 수 있는 경우는 두가지로 경우를 나누어 생각하면 된다.
- 첫번째 열(또는 행)이 흰색(W)으로 시작하거나
- 첫번째 열(또는 행)이 검은색(B)으로 시작하거나
이 문제는…. 처음에 체스판을 어떤식으로 쪼개서 조회해야 하는지, 경우의 수에 따라 조건문을 어떻게 설정해야 할지에 대해 고민하느라 시간이 꽤 많이 소요되었다.
내가 생각해낸 아이디어는 다음과 같다.
- 임의의 8*8 면적의 시작점 위치를 (row, col)로 정의
- (row, col)위치의 값이 B인지 W인지에 따라 나머지 값들을 조건문으로 체크
- 변수 row와 col은 한번의 while문이 끝날 때마다 갱신함으로써 8*8면적을 가질 수 있는 ‘모든’ 경우의 수를 탐색. 즉, while문이 1회 실행되면 시작점 인덱스 (row, col)을 기준으로 이중 for문을 통해 (8x8)정사각형 면적 전체를 1회 탐색하는 꼴이다.
- 시작점(row, col)의 행과 열이 짝수인지, 홀수인지에 따라 경우를 나누어 현재 탐색할 지점(i, j)과 비교함으로써 B/W 를 따진다.
- 즉 다음과 같이 두가지 안의 두가지 경우 총 네가지로 경우를 나누었다..
- 현재 탐색중인 행(i)이 시작점 행(row)과 같은 계열(짝수 or 홀수)이라면, i행은 (row, col)행과 같은 규칙으로 색깔이 배치되어야 한다.
- 이 중에서도 현재 탐색중인 열(j)이 시작점 열(col)과 같은 계열(짝수 or 홀수)이라면, (i, j)의 값은 (row, col)값과 같아야 한다.
- 반대로, 다른 계열(짝수 or 홀수)이라면, (i, j)의 값은 (row, col)값과 달라야 한다.
- 현재 탐색중인 행(i)이 시작점 행(row)과 다른 계열(짝수 or 홀수)이라면, i행은 (row, col)행과 반대의 규칙으로 색깔이 배치되어야 한다.
- 이 중에서도 현재 탐색중인 열(j)이 시작점 열(col)과 같은 계열(짝수 or 홀수)이라면, (i, j)의 값은 (row, col)값과 달라야 한다.
- 반대로, 다른 계열(짝수 or 홀수)이라면, (i, j)의 값은 (row, col)값과 같아야 한다.
내가 간과했던 점이 시작점을 기준으로 체스판을 바꾸려고 할 때가 무조건 최솟값이라고 생각을 했다는 것이다.
그렇지 않 다 count가 64/32 보다 클 경우, 즉 절반 이상의 색을 바꿔야 하는 경우
count로 측정된 값들보다 그 나머지 값들(64-count)을 바꾸는 것이 오히려 효율적이다!
이 점을 캐치하지 못해서 삽질 시간이 길어졌다.
다음과 같이 4x4 사이즈의 체스판이 주어졌다고 가정한다.(문제에서는 가로세로 8이상이지만)
WBBB
BWBB
BWBW
WBWB
위 아이디어대로라면 시작점인 (0, 0)의 값은 W이고
W를 기준으로 다음과 같이 색칠해야 할 값 count는 총 10 이다.
WB'B'B
BWB'B'
'BWBW'
'WBWB'
하지만 이 경우 10번을 색칠해서 바꿀 바에는 16칸 중 10칸을 제외한 나머지 6칸을 바꾸는 것이 더 효율적이며 최솟값이다.
따라서 8*8인 64칸에서 count 값을 빼주는 코드를 추가하게 되었다!
나처럼 이해가 어려웠던 분들에게 도움이 되었으면 좋겠다.
시도해본 반례들 정리_디버깅 해보세요
#INPUT:
10 10
WWBBWWWBBW
WBBWBWWWWB
WBWBWWBBWW
WBBBBBBBWW
WBBWWWBWWW
WBBBBBWWBB
WWBWWBWWBB
BWWBBWWWBB
BBWBBBBBWB
WWWBBBWWWB
#OUTPUT: 30
#INPUT:
8 8
BBBBWBBW
WWWWBBWB
WWBBWBWW
WBWWBWBW
WBBWBBWB
BWBWBWWB
BWWWWWBW
BWBBBBWW
#OUTPUT: 29
#INPUT:
16 16
BBBBBBBBWBWBWBWB
BBBBBBBBBWBWBWBW
BBBBBBBBWBWBWBWB
BBBBBBBBBWBWBWBW
BBBBBBBBWBWBWBWB
BBBBBBBBBWBWBWBW
BBBBBBBBWBWBWBWB
BBBBBBBBBWBWBWWW
BBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBB
#OUTPUT: 1
#INPUT:
8 8
WWBBBBBB
WBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
#OUTPUT: 31
개인적으로 이 문제…. 테스트케이스 몇 개 더 추가해주셨음 좋겠다 제발 엉엉엉헝헝 다음은 채점 통과된 코드!
n, m = map(int, input().split())
#체스판 생성
board = []
for i in range(n):
row = list(input())
board.append(row)
row = 0
col = 0
result = []
start_char = ''
while row+8 <= n:
cnt = 0
start_char = board[row][col] #시작점 문자 판별
for i in range(row, row+8):
r = board[i]
for j in range(col, col+8):
if i % 2 == row % 2:
#시작행과 같은 종류(짝,홀수)일때.
if start_char == 'W':
#최초 문자가 W일 때
if j % 2 == col % 2:
#시작열과 같은 종류(짝,홀수)일때.
if r[j] != 'W':
cnt += 1
else:
if r[j] != 'B':
cnt += 1
else:
#최초 문자가 B일 때.
if j % 2 == col % 2:
if r[j] != 'B':
cnt += 1
else:
if r[j] != 'W':
cnt += 1
else:
if start_char == 'W':
#최초 문자가 W일 때
if j % 2 == col % 2:
if r[j] != 'B':
cnt += 1
else:
if r[j] != 'W':
cnt += 1
else:
#최초 문자가 B일 때.
if j % 2 == col % 2:
if r[j] != 'W':
cnt += 1
else:
if r[j] != 'B':
cnt += 1
#if row == 1 and col == 2:
# print(row, 'i=', i, 'j=', j, cnt)
#추가한 부분
if cnt > n*m/2:
cnt = 64 - cnt
#8x8면적 한번 조회할 때 마다 결과값 모아두기
result.append(cnt)
if col+8 == m:
#가장 끝 열까지 조회했다면 시작점을 다음 행으로 이동.
row += 1
col = 0
else:
col += 1
#결과값 배열에서 최소값 찾아 출력
print(min(result))
채점 결과
