[Algorithm] 백준 1018

ZEDY·2024년 3월 11일

[코딩테스트] 알고리즘 문제풀이

목록 보기

8/46

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

풀이

나는 원래 두가지 케이스의 체스판에 대해 미리 선언을 해놓고, 비교해서 차이를 반환하려고 하였다.
근데 그거를 어떻게 한번에 처리할 수 있는지 고민이었고, 만약 직접 비교하는 연산을 수행한다면 테이블을 괜히 저장하는 것이기 때문에 필요없는 공간을 차지할 것이라고 생각했다.

근데 또 생각해보니까 연산을 안하니까 처리는 빨리 될거 같기도 하네..

내가 생각한 알고리즘

값을 입력 받는다
체스판 입력 받는다
체스판의 차이를 계산한다.
계산한 차이값이 최소라면 갱신해 저장한다.

코드

a, b = map(int, input().split(' '))
table = []
min_diff = 64

# 체스판 입력 받기
for _ in range(a):
    row = input().strip()
    table.append(row)

# 8x8 체스판의 차이 계산하기
def check_diff(start_i, start_j):
    case_B_cnt = 0
    case_W_cnt = 0
    for x in range(8):
        for y in range(8):
            if (x + y) % 2 == 0:
                if table[start_i + x][start_j + y] == 'B':
                    case_W_cnt += 1
                else:
                    case_B_cnt += 1
            else:
                if table[start_i + x][start_j + y] == 'W':
                    case_W_cnt += 1
                else:
                    case_B_cnt += 1
    return min(case_B_cnt, case_W_cnt)

# 모든 가능한 시작 위치에 대해 8x8 체스판을 확인
for i in range(a - 7):
    for j in range(b - 7):
        min_diff = min(min_diff, check_diff(i, j))

print(min_diff)

개선

위에서 내가 언급한 걸로 구현해보겠다.

내가 생각한 알고리즘

미리 체스판 2가지 케이스를 그려놓기
비교하기

마주한 문제

체스판을 어떻게 정의할 것인가?
나는 인덱스로 접근하고 싶었기 때문에 다음과 같이 정의했다.
case_B = [['BWBWBWBW'], ['WBWBWBWB'], ['BWBWBWBW'], ['WBWBWBWB'], ['BWBWBWBW'], ['WBWBWBWB'], ['BWBWBWBW'], ['WBWBWBWB']]
case_W = [['WBWBWBWB'], ['BWBWBWBW'], ['WBWBWBWB'], ['BWBWBWBW'], ['WBWBWBWB'], ['BWBWBWBW'], ['WBWBWBWB'], ['BWBWBWBW']]

case_B[i][j]

근데 이렇게 하면 접근이 안된다.
이유는 리스트 안에 리스트 안에 문자열이 있어서 접근이 안되는 거였다.
#### 해결한 방법
그렇다면 다음과 같이 선언을 해주면 된다.
``` python
# case_B = [['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
#           ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
#           ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
#           ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
#           ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
#           ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
#           ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
#           ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B']]

# case_W = [['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
#           ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
#           ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
#           ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
#           ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
#           ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
#           ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
#           ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W']]

case_B = ['BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB']
case_W = ['WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW']

이렇게 하면 인덱싱이 잘 된다.

개선한 코드

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

case_B = ['BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB']
case_W = ['WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW']
table = []
min_diff = 64

# 체스판 입력 받기
for _ in range(a):
    row = input().strip()
    table.append(row)

# 8x8 체스판의 차이 계산하기
def check_diff(start_i, start_j):
    case_B_cnt = 0
    case_W_cnt = 0
    for x in range(8):
        for y in range(8):
            if (case_B[x])[y] != table[start_i + x][start_j + y]:
                case_B_cnt += 1
            if (case_W[x])[y] != table[start_i + x][start_j + y]:
                case_W_cnt += 1
    return min(case_B_cnt, case_W_cnt)

# 모든 가능한 시작 위치에 대해 8x8 체스판을 확인
for i in range(a - 7):
    for j in range(b - 7):
        min_diff = min(min_diff, check_diff(i, j))

print(min_diff)

근데 뭐가 더 효율적인가?

주어진 두 코드 모두 8x8 체스판의 차이를 계산하여 최소 차이를 구하는 것을 목표로 하고 있습니다. 그러나 두 가지 접근 방식 간에는 몇 가지 차이점이 있습니다:

문자열과 리스트의 사용:
- 첫 번째 코드에서는 case_B와 case_W를 각각의 문자열로 정의하고, 문자열의 각 위치에 대해 직접 접근합니다.
- 두 번째 코드에서는 case_B와 case_W를 각각의 문자열 리스트로 정의하고, 리스트의 각 요소에 접근하여 비교합니다.
접근 방식의 차이:
- 첫 번째 코드에서는 각 위치마다 'B' 또는 'W'와 비교하여 최소 차이를 계산합니다.
- 두 번째 코드에서는 미리 정의된 패턴과 실제 체스판 각 위치의 문자를 비교하여 최소 차이를 계산합니다.
코드 복잡성:
- 두 번째 코드에서는 미리 정의된 패턴과 체스판을 비교하는 방식을 사용하므로 코드가 더 간단해 보입니다.
- 하지만 두 번째 코드에서는 미리 정의된 패턴을 정확하게 구성해야 합니다.
실행 시간:
- 실제로 코드의 실행 시간은 입력값과 체스판의 크기에 따라 달라집니다. 두 코드 모두 입력값의 크기와 상관없이 시간 복잡도가 일정합니다.