[Programmers] 고고학 최고의 발견

문제

N x N 격자의 시계들(0:12시, 1:3시, 2:6시, 3:9시)이 상하좌우 연동되어 돌 때, 모든 시계를 12시(0)로 맞추기 위한 최소 조작 횟수를 구하는 문제. 시계 하나를 돌리면 본인 및 상하좌우 시계가 함께 90도(1칸)씩 돌아가고, 0(12시), 1(3시), 2(6시), 3(9시) 이며, 4번에 1바퀴 회전. 제한 조건은 N이 2 이상 8 이하.

회고

풀다가 막혔다. 처음에는 주변 시계가 0이 아닌 곳을 찾아 돌리는 탐욕적(Greedy) 방식을 사용했지만, 너무 많은 경우의 수가 존재하는데다 애초에 돌려서 상하좌우가 0이 아닌 상태가 되더라도 전체를 맞추기 위해 돌려야 하는 경우가 존재했다.

 

이러한 문제를 푸는데는 정석적인 방법으로 라이츠 아웃(Lights Out) 퍼즐의 해결 방법을 도입해야 한다. 첫 번째 행(Row 0)이 결정되면 나머지 행의 조작이 강제되는 로직이 중요한 키. 첫 번째 행을 완전탐색해서 돌린 다음 2~N까지 행은 윗 행에 맞춰 빠르게 계산한 다음 마지막 행이 0이 되는지만 체크하고, 만약 조건을 만족한다면 결과값과 비교해 더 작은 값으로 갱신하는 방식으로 해결이 가능하다.

 

from itertools import product

def solution(clockHands):
    answer = 1e9
    n = len(clockHands)
    d = [(-1,0), (1,0), (0,0), (0,-1), (0,1)]

    for first in product(range(4), repeat = n):
        clock = []
        cnt = sum(first)

        for clock_row in clockHands:
            one_row = []
            for clock_num in clock_row:
                one_row.append(clock_num)
            clock.append(one_row)

        for i, f in enumerate(first):
            y, x = 0, i
            for dy, dx in d:
                ny, nx = y+dy, x+dx
                if 0 <= ny < n and 0 <= nx < n:
                    clock[ny][nx] = (clock[ny][nx]+f)%4

        for i in range(1, n):
            ex_row = clock[i-1]
            for j, k in enumerate(ex_row):
                if k != 0:
                    m = 4-clock[i-1][j]
                    cnt += m
                    for dy, dx in d:
                        ny, nx = i+dy, j+dx
                        if 0 <= ny < n and 0 <= nx < n:
                            clock[ny][nx] = (clock[ny][nx]+m)%4

        if set(clock[-1]) == {0}:
            answer = min(answer, cnt)
            print(answer, cnt)

    return answer