체스판 다시 칠하기

문제 출처

내가 작성한 코드

def findFit(li, i, j):
    cnt = 0
    s = li[i][j] # 현재 위치를 체스판 시작점으로 선언
    for y in range(8):
        for x in range(8):
            if (x + y) % 2 == 0 and li[i + y][j + x] != s:
                cnt += 1
            elif (x + y) % 2 == 1 and li[i + y][j + x] == s:
                cnt += 1
    cnt2 = 0
    for y in range(8):
        for x in range(8):
            if (x + y) % 2 == 0 and li[i + y][j + x] == s:
                cnt2 += 1
            elif (x + y) % 2 == 1 and li[i + y][j + x] != s:
                cnt2 += 1
    if cnt < cnt2:
        return cnt
    return cnt2

y, x = map(int, input().split())
li = []
for i in range(y):
    str = input()
    li.append(str)

min = findFit(li, 0, 0)
for i in range(y - 7):
    for j in range(x - 7):
        fit = findFit(li, i, j)
        if min > fit:
            min = fit
print(min)

문제를 풀기위해 고민한 것

• 완전탐색을 할수록 똑같은 범위의 체스판을 검사해야하기때문에 규칙성이 있는 부분은 검사를 하지 않는방법을 생각했었다. 하지만 이 방법은 시작 타일의 색과 바뀌는 인덱스에 따라 식별하기 어려웠고, 불규칙한 입력의 균일하지않은 규칙의 타일을 기록하는 것이 비효율적이라 판단했다.
• 시작 타일의 좌포를 첫 이중반복문으로 받으며 불필요한 색을 식별하고자 하였다.
• 시작타일의 색을 기준으로 규칙적인 타일의 인덱스를 식별하기위해서 좌표x + y값이 짝수인 색들이 시작 타일의 색과 일치하면 된다는 규칙을 발견하여 적용하였다.
  -> 그렇지만, 시작 타일의 색이 부적절할 수 있기때문에 그의 반대의 상황또한 식별하여 비교하였다.

내 코드의 아쉬운 점

다른 블로그의 풀이를 보니 방법은 같지만 가독성이 더 좋다고 느꼈다.

• findFit()함수 내에 for i in range(8)로 두고 내부 index에 i를 더해서 계산하였는데 for i in range(i, i + 8)로 두는것이 더 명확한 코드인 것 같다.
• 아래의 코드로 수정하면 더 좋을 것 같다.

def findFit(li, i, j):
    cnt = 0
    cnt2 = 0
    s = li[i][j] # 현재 위치를 체스판 시작점으로 선언
    for y in range(i, i + 8):
        for x in range(j, j + 8):
            if (x + y) % 2 == 0:
            	if li[y][x] != s:
	                cnt += 1
                else:
                	cnt2 += 1
            else:
				if li[y][x] == s:
	                cnt += 1
                else:
                	cnt2 += 1
    if cnt < cnt2:
        return cnt
    return cnt2

결과

수정한 결과 시간도 단축이 되었다. 아무래도 함수 내에서 2중반복을 한번만 하기 때문인 것같다.