고고학 최고의 발견 - Python, product

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/131702

프로그래머스

 

 

코드 & 풀이

 

from itertools import product
import copy

def solution(clockHands):
    N = len(clockHands)
    direct = [(-1, 0), (1, 0), (0, 0), (0, -1), (0, 1)]  # 위, 아래, 현재, 왼쪽, 오른쪽

    def rotate(board, x, y, count):
        for dx, dy in direct:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < N:
                board[nx][ny] = (board[nx][ny] + count) % 4

    min_moves = float('inf')
    for first_row in product(range(4), repeat=N):  # 첫 번째 행의 모든 회전 경우 탐색
        board = copy.deepcopy(clockHands)  # 원본을 유지하기 위해 복사
        moves = 0

        # 첫 번째 행을 first_row에 맞게 회전
        for j in range(N):
            if first_row[j] > 0:
                rotate(board, 0, j, first_row[j])
                moves += first_row[j]

        # 두 번째 행부터 순차적으로 처리
        for i in range(1, N):
            for j in range(N):
                if board[i - 1][j] != 0:
                    cnt = 4 - board[i - 1][j]
                    rotate(board, i, j, cnt)
                    moves += cnt

        # 마지막 행이 전부 0인지 확인
        for j in range(N):
            if board[N - 1][j] != 0:
                break
        else:
            min_moves = min(min_moves, moves)

    return min_moves

 

 

모든 회전의 경우의 수를 시도할 필요는 없다.

 

첫번째 줄에 대한 경우의 수가 나오면

 

밑의 줄은 결국 자신의 윗칸이 0인지 아닌지에 따라 회전해야하기 떄문이다.

 

그렇기에 product를 통해

 

4자리를 0~3의 경우의 수를 모두 구한 후

 

진행을 해주면 됩니다.

 

그리고 마지막 줄이 0으로, 즉 12시를 가르키고 있는지 검사 후

 

최소값을 갱신해주면 됩니다.

 

 

 

다음에 또 봐요