20210204_코테공부

# 17406 배열 돌리기 4 (골드4)

• 다시 풀어보기
• Point. DFS, 방향벡터, 백트레킹 기법 사용

from copy import deepcopy

N, M, K = map(int, input().split()) # 배열 A크기 N,M, 회전 연산 개수 K
A = [list(map(int,input().split())) for _ in range(N)] # 배열 A 수
Q = [tuple(map(int, input().split())) for _ in range(K)] # 회전 연산 정보
dx,dy = [1,0,-1,0],[0,-1,0,1]   # 방향벡터 남서북동
ans = 10000 # 배열 A의 값의 최솟값

def value(arr): # 행의 최소값
    return min([sum(i) for i in arr])

def convert(arr, qry): # 회전
    (r, c, s) = qry # 중심점 (r,c) 거리 s
    r, c = r-1, c-1 # 좌표가 0,0 시작이기 때문에 -1 해줌
    new_arr = deepcopy(arr)
    for i in range(1, s+1):
        rr, cc = r-i, c+i
        for w in range(4): # 방향 4번 바꿈
            for d in range(i*2): #
                rrr, ccc = rr + dx[w], cc+dy[w]
                new_arr[rrr][ccc] = arr[rr][cc]
                rr, cc = rrr, ccc
    return new_arr

def dfs(arr, qry):
    global ans # 전역변수 설정
    if sum(qry) == K: # 쿼리를 다 처리했을 경우
        ans = min(ans, value(arr)) # 최소값 저장
        return
    for i in range(K):
        if qry[i]:
            continue
        new_arr = convert(arr, Q[i]) # 쿼리 회전
        qry[i] = 1  # 백트래킹 기법
        dfs(new_arr, qry)
        qry[i] = 0

dfs(A,[0 for i in range(K)])
print(ans)

 

단계별풀기 - 브루트 포스

# 1018 체스판 다시 칠하기(실버5) (참고)

• 크기가 n*m이고, 흰색과 검은색으로 막 칠해져 있는 보드판이 있다.
• 이 보드판을 잘라서 8*8크기의 체스판을 만들려고 한다.
• 체스판은 흰색과 검은색이 번갈아가며 체크무늬를 이루어야한다.
• 보드판을 잘라서, 체스판을 만들기 위해서 알맞게 색을 고쳐서 체크무늬를 만들어야 한다.
• 고쳐야 하는 색의 최소값을 구하라
• Point. 인덱스 합이 짝수인지 홀수인지로 체크무늬를 판단할 수 있다.

n, m = map(int, input().split())
board = list()
mini = list()

for _ in range(n):
    board.append(input())

for a in range(n - 7): # 8*8로 자르기
    for i in range(m - 7):
        idx1 = 0
        idx2 = 0
        for b in range(a, a + 8):
            for j in range(i, i + 8):              # 8X8 범위를 B와 W로 번갈아가면서 검사
                if (j + b)%2 == 0:
                    if board[b][j] != 'W': idx1 += 1
                    if board[b][j] != 'B': idx2 += 1
                else :
                    if board[b][j] != 'B': idx1 += 1
                    if board[b][j] != 'W': idx2 += 1
        mini.append(idx1)                          # W로 시작했을 때 칠해야 할 부분
        mini.append(idx2)                          # B로 시작했을 때 칠해야 할 부분

print(min(mini))

 

ex) n = 10, m = 13일 경우 len(mini) = (10-7)*(13-7)*2 = 36개 그 값들 중 가장 작은 수 출력