백준 1018번 문제(체스판 다시 칠하기) 파이썬(Python) 풀이 [로밍맨]

문제 링크

www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

 

정답 코드는 아래와 같습니다.

N = 8
str1 = "WBWBWBWB"
str2 = "BWBWBWBW"
pivot1 = [ str1, str2, str1, str2, str1, str2, str1, str2 ]
pivot2 = [ str2, str1, str2, str1, str2, str1, str2, str1 ]
 
def solve():
  a, b = [int(x) for x in input().split()]
  arr = []
  for i in range(a):
    arr.append(input())
  rst = float('inf')
  for i in range(a-N+1):
    for j in range(b-N+1):
      count = 0
      for p in range(N):
        for q in range(N):
          if arr[i+p][j+q] != pivot1[p][q]:
            count += 1
      rst = min(rst, count)
      count = 0
      for p in range(N):
        for q in range(N):
          if arr[i+p][j+q] != pivot2[p][q]:
            count += 1
      rst = min(rst, count)
  print(rst)
 
solve()
 

 

이 문제에 대한 저의 풀이는 단순하게 모든 경우에 대해서 모든 값을 다 비교해보고 그 중에서 가장 작은 값을 출력하는 것입니다.

기준(pivot)이 되는 체스판은 2개가 있습니다.

하나는 흰 칸부터 시작하는 것(pivot1)이고, 다른 하나는 검은 칸부터 시작하는 것(pivot2) 입니다.

각 라인이 중복적으로 발생하기 때문에 위 코드와 같이 라인을 2개 먼저 만들어 놓고 그걸 연달아서 이어 붙여서 pivot1 과 pivot 2를 아래와 같이 만듭니다.

 

<pivot1>

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

 

<pivot2>

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

 

728x90

 

그 다음에는 입력으로 주어진 체스판의 (0,0) 위치부터 (a-8+1, b-8+1) 위치까지 모든 경우에 대해서 다시 칠해야 하는 칸의 갯수를 구합니다.

(a-8+1, b-8+1) 까지만 하는 이유는 이 위치를 넘어가면 주어진 판 위에 8X8 의 체스판을 덮었을 때, 뒷 부분은 겹치지 않기 때문입니다.

이제 각 경우들에 대해서 다시 칠해야 하는 칸의 갯수를 구합니다.

pivot1 에 대해서도 구하고 pivot2 에 대해서도 구합니다.

문제의 정답은 모든 값 중에서 가장 작은 값이기 때문에 가장 작은 값만을 유지해주었다가 마지막에 출력해줍니다.

 

풀이는 아래 영상 참고 바랍니다.

www.youtube.com/watch?v=98TMUoYCCEE

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)