[프로그래머스] 고고학 최고의 발견

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

프로그래머스

 

분석

1. 시곗바늘은 시계방향으로만 돌릴 수 있고 한 번의 조작으로 90도씩 돌릴 수 있습니다.
2. 시계들은 기계장치에 의해 연결되어 있어 어떤 시계의 시곗바늘을 돌리면 그 시계의 상하좌우로 인접한 시계들의 시곗바늘도 함께 돌아갑니다.
3. 각 시계는 12시, 3시, 6시, 9시 방향 중의 한 방향을 가리키고 있습니다.
4. 각 시계의 시곗바늘을 적절히 조작하여 모든 시곗바늘이 12시 방향을 가리키면 퍼즐이 해결되어 성궤를 봉인하고 있는 잠금장치가 열릴 것입니다.
5. clockHands[i]의 원소들은 시곗바늘의 방향을 나타내며 0은 12시 방향, 1은 3시 방향, 2는 6시 방향, 3은 9시 방향을 나타냅니다.

•  첫째 행부터 차례대로 내려온다면, 첫째 행은 둘째 행에, 둘째 행은 셋째 행에, 이런 식으로 n-1번째 행은 n번째 행의 좌표에 종속적
• 한 행당 경우의 수 4⁸ : 8(2⁴)가지를 0~3번 돌리는 경우 4가지
• 완전탐색 4⁶⁴ ⇒ 첫째 행만 탐색 4⁸
• 첫째 행에 대해 조작이 이루어졌다면 나머지는 해당 라인을 회전하여 12시로 가게끔 만든 후 마지막 라인을 체크하여 모두 12시에 갔는지 확인하고, 확인이 되었다면 answer에 최솟값을 갱신

풀이

from itertools import product
dr=[0,0,0,1,-1]
dc=[0,1,-1,0,0]

def solution(clockHands):
    answer=int(1e9)
    
    n=len(clockHands)
    
    def calc(r,c):
        temp=0
        for d in range(5):
            nr,nc = r+dr[d], c+dc[d]
            if 0<=nr<n and 0<=nc<n:
                temp+=data[nr][nc]
        return (clockHands[r][c]+temp)%4

    
    for li in product(range(4), repeat=n):
        data=[[0]*n for _ in range(n)]
        
        data[0]=list(li) # 1행
        for i in range(1,n): # 2~(n-1)행
            for j in range(n):
                data[i][j]=(4-calc(i-1,j))%4

        for i in range(n):
            if calc(n-1, i) !=0:
                break
        else:
            temp=sum([sum(t) for t in data])
            answer= min(answer, temp)
                

    return answer