고고학 최고의 발견

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

고고학 최고의 발견 연습문제 Lv. 3 62명 4%

 

요약

첫 번째 줄이 결정되면, 두 번째 줄도 1가지 케이스로 결정된다. 
첫 번째 줄의 모든 케이스를 전수조사(BF)한다. 

 

꽤 힘들게 풀었다 ㅠ,.ㅠ 레벨 3 맞음?

첫 줄이 결정되면 다음 줄의 답도 결정된다. 
(상하좌우 방향은 관계 없다.)

첫 줄이 3, 0, 3, 0 으로 결정되어 있다면
다음 줄은 1, 0, 1, 0 회전하는 케이스만 존재한다.  

그럼 첫 줄은 어떻게 결정할까? 
첫 줄과 두 번째 줄은 서로 영향을 주기 때문에.. 
복잡한 문제다. 

첫 줄을 3, 3, 3, 0 에서 1번 턴을 해서
0, 0, 0, 0 으로 만들었더라도 
두 번째 줄의 상황에 따라 최적의 해가 아닐 수가 있다. 

가장 얄팍한 해결책은
첫 번째 줄과 두 번째 줄의 '모든' 케이스를 체크해서
첫 번째 줄을 0, 0, 0, 0 으로 만드는 최소의 회전 수를 찾는 방법이다. 

경우의 수는 4**8 = 65536, 코드는 작동했으나,
당연히 시간제한. 

코드가 작동하는 걸 확인했으니
이것을 어떻게 최적화할까..

첫 줄의 모든 경우의 수를 뽑으면 4**4 = 256
이 정도는 BF(전수조사) 해볼 만한 숫자다. 

첫 줄의 모든 케이스를 만든 뒤,
이를 바탕으로 다음 줄을 결정하고.
마지막 줄까지 결정되면
전체가 0이 맞는지 확인하고
턴 수의 최솟값을 모으면 답이 나온다. 

첫 줄의 성공 여부을 먼저 확인하지 않고,
마지막으로 미루는 것이 오히려 간단하다.  

다음 줄 결정에
복잡한 연산이 필요 없기 때문에
가능한 시나리오이다. 

from copy import deepcopy


def solution(clocks):
    def mask_generator():  # 0 번 라인의 시계 바늘을 얼마나 돌릴 지 모든 경우를 만듬
        for i in range(4 ** length):
            mask = []
            while i:
                mask.append(i % 4)
                i //= 4
            yield mask + [0] * (length - len(mask))

    def check_all(board):  # 모든 시계의 0시 체크
        for row in board:
            for each in row:
                if each != 0:
                    return False
        return True

    def turn_clock(y, x, time, board):  # 시계 바늘을 돌려준다.
        for dy, dx in ((-1, 0), (0, -1), (0, 0), (0, 1), (1, 0)):
            if 0 <= (ny := y + dy) < length and 0 <= (nx := x + dx) < length:
                board[ny][nx] = (board[ny][nx] + time) % 4

    def turn_line(line_num, board):  # 윗 줄의 시계 바늘에 따라 아래 시계의 바늘 회전
        turns = 0
        for index, each in enumerate(board[line_num - 1]):
            if each > 0:
                turn_num = 4 - each
                turn_clock(line_num, index, turn_num, board)
                turns += turn_num
        return turns

    def solve():
        min_turn = float("inf")
        for mask in mask_generator():  # 모든 경우를 만듬.
            board = deepcopy(clocks)  # 2차원 배열의 복사에 딥카피 필요. 
            for index, turn_num in enumerate(mask):  # mask를 board에 적용. 0번 줄 회전. 
                turn_clock(0, index, turn_num, board)  # 이거 삽질이다. 그냥 mask를 바로 1열에
            turns = sum(mask)  # mask의 합 = 지금까지 회전수
            for line_num in range(1, length):
                turns += turn_line(line_num, board)
            if check_all(board):  # 체크
                min_turn = min(min_turn, turns)
        return min_turn

    length = len(clocks)
    return solve()

코드를 조금 수정했다...

product 를 잊고 있었다. 
그리고 마지막 줄만 체크하면 되는데... 

from copy import deepcopy
from itertools import product


def solution(clocks):
    def check_row(row):  # 시계의 0시 체크
        for each in row:
            if each != 0:
                return False
        return True

    def turn_clock(y, x, time, board):  # 시계 바늘을 돌려준다.
        for dy, dx in ((-1, 0), (0, -1), (0, 0), (0, 1), (1, 0)):
            if 0 <= (ny := y + dy) < length and 0 <= (nx := x + dx) < length:
                board[ny][nx] = (board[ny][nx] + time) % 4

    def turn_line(line_num, board):  # 윗 줄의 시계 바늘에 따라 아래 시계의 바늘 회전
        turns = 0
        for index, each in enumerate(board[line_num - 1]):
            if each > 0:
                turn_num = 4 - each
                turn_clock(line_num, index, turn_num, board)
                turns += turn_num
        return turns

    def solve():
        min_turn = float("inf")
        for mask in product(range(4), repeat=length):  # 모든 경우를 만듬.
            board = deepcopy(clocks)  # 2차원 배열의 복사에 딥카피 필요. 
            for index, turn_num in enumerate(mask):  # mask를 board에 적용. 0번 줄 회전. 
                turn_clock(0, index, turn_num, board)
            turns = sum(mask)  # mask의 합 = 지금까지 회전수
            for line_num in range(1, length):
                turns += turn_line(line_num, board)
            if check_row(board[length - 1]):
                min_turn = min(min_turn, turns)
        return min_turn

    length = len(clocks)
    return solve()