[프로그래머스] 131702번 고고학 최고의 발견 풀이 (Python)

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

프로그래머스

 

 

이 문제를 완전탐색으로 푼다면 시간복잡도는 O(4**64)로, 완전탐색은 불가능하다.

시계를 하나 돌리면 주변까지 돌아가기 때문에, 아무데나 돌리면 안된다.

이 문제의 핵심은 맨 윗줄만 완전탐색을 하고 나머지는 앞의 줄에 종속적이란것이다. O(4**8)

 

이해를 돕기위해 비루하지만 PPT로 쉽게 나타내봤다...

초기 예시 상태.맨 첫줄은 0,1,1,0의 회전이 필요하다.

이해를 돕기 위해 변한후 상태를 빨강으로 표시했다.두번째 줄은 앞의 줄에따라 0,1,1,0의 회전이 필요:)

 

 

최종적으로 마지막 줄이 모두 ↑이니, 정답.

이를 정리하면 다음과같다.

먼저 맨 윗줄에서 모든 누름 조합을 시도해본다.(완전 탐색)

윗줄이 결정되면 -> 2번째 줄은 1번째 줄을 맞추려고누르고

->3번째 줄은 2번째 줄을 맞추려고 누른다.

마지막 줄까지 갔을 때 다 12시 방향이면 성공이다.

그런 경우 중에서 가장 적은 누름 횟수를 정답으로 한다.

 

대략적인 코드 흐름은 아래와 같다.

for 모든 가능한 첫 줄 누르기 조합:
    현재 퍼즐 상태 = 원본 복사

    첫 줄을 누른다 (지정된 횟수만큼)

    아래 줄부터는 위 칸을 맞추기 위해 강제적으로 누른다

    마지막 줄이 전부 0이면 성공 → 최소 횟수 갱신

 

코드

from itertools import product
from copy import deepcopy

def solution(clockHands):
    directions = [(-1,0),(1,0),(0,1),(0,-1),(0,0)]
    N = len(clockHands)
    answer = int(1e9)

    # 첫 번째 줄의 모든 누름 조합 (0~3)
    for first_row in product(range(4), repeat=N):
        new_board = deepcopy(clockHands)
        cnt = 0
        
        # 첫 줄 누르기
        for c, times in enumerate(first_row):
            if times:
                for dx, dy in directions:
                    nx, ny = 0 + dx, c + dy
                    if 0 <= nx < N and 0 <= ny < N:
                        new_board[nx][ny] = (new_board[nx][ny] + times) % 4
                cnt += times  # 조작횟수 누적

        # 두 번째 줄부터는 위 줄 맞추기 위해 자동 누르기
        for r in range(1, N):
            for c in range(N):
                times = (4 - new_board[r - 1][c]) % 4
                if times:
                    for dx, dy in directions:
                        nx, ny = r + dx, c + dy
                        if 0 <= nx < N and 0 <= ny < N:
                            new_board[nx][ny] = (new_board[nx][ny] + times) % 4
                    cnt += times

        # 마지막 줄이 모두 0인지 확인
        if all(x == 0 for x in new_board[-1]):
            answer = min(answer, cnt)

    return answer