[ 위클리 챌린지 ] [ 3주차 ] 퍼즐 조각 채우기

풀이 과정

---

• 1, 2주차에 비해 난이도가 극악무도해져서 최대한 나중에 풀음ㅜㅜ
• 전체적으로 세개의 과정으로 나눌 수 있다.
  1. board에서 빈 블록 구하기
  2. table에서 넣을 블록 구하기
  3. (1)번에서 구한 빈 블록에 (2)번에서 구한 블록들을 1번, 2번, 3번, 4번 회전시키면서 넣어보고 맞는지 확인

1. board에서의 빈 블록과, table에서 넣을 블록들을 bfs로 구한다.
   • 이 때, 편의를 위해 블록들을 최대한 왼쪽 위로 붙여준다.
   • 예시로 4,4->4,5->4,6 블록을 (0,0 -> 0,1 -> 0,2)로 바꾸어 준다.
   • 방식은 블록들의 행의 최솟값과 열의 최솟값을 전체 블록에 빼주면 된다.
2. 블록 회전을 구현한다.
   • 블록 회전은 각 블록이 [행, 열]에 있을 때,
   • 회전된 블록은 [(블록들의 최대 열 - 현재 열), 행] 위치를 갖게 된다.
3. 이제 빈 블록에 대해서 블록들이 들어가는지 확인한다.
   • 블록을 4번 회전시키면 다시 자기자신으로 돌아오므로, 4번 회전시키면서 각각의 경우의 수에 대해 들어가는지 확인
   • 확인할 때 방식은 블록들과 빈 블록의 교집합을 하여, 교집합의 원소의 개수가 블록의 개수와 일치하면 블록이 들어가는것이다.

• 풀고나서 돌아보니 엄청 어려웠던것 같진 않은데.. 풀때는 되게 고민을 많이 한 문제였던 것 같다.

---

소스 코드

---

from collections import deque

def get_movement(arr, position, org_value, change_value):
    # board의 경우 org_value, change_value가 0, 1
    # table의 경우 org_value, change_value가 1, 0

    x, y = position[0], position[1]
    movement = [[x, y]]
    queue = deque([[x, y]])
    arr[x][y] = change_value
    min_x, min_y = x, y
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    length = len(arr)

    while queue:
        nx, ny = queue.popleft()
        for i in range(4):
            mx, my = nx + dx[i], ny + dy[i]
            if 0 <= mx < length and 0 <= my < length and arr[mx][my] == org_value:
                arr[mx][my] = change_value
                min_x, min_y = min(mx, min_x), min(my, min_y)
                movement.append([mx, my])
                queue.append([mx, my])

    movement = list(map(lambda f:(f[0]-min_x, f[1]-min_y), movement))
    return movement

def get_total_list(arr, f, value):
    length = len(arr)
    total_list = []
    org_value = value
    change_value = 1 if value == 0 else 0
    for i in range(length):
        for j in range(length):
            if arr[i][j] == value:
                total_list.append(f(arr, [i, j], org_value, change_value))

    return total_list

def rotate(block):
    max_col = max(map(lambda x:(x[1]), block))
    return list(map(lambda x:(max_col-x[1], x[0]), block))


def solution(game_board, table):
    answer = 0
    total_blank = get_total_list(game_board, get_movement, 0)
    total_block = get_total_list(table, get_movement, 1)
    used = [False] * len(total_block)
    for idx1, blank in enumerate(total_blank):
        for idx2, block in enumerate(total_block):
            if used[idx2] or len(blank) != len(block):
                continue

            temp = block
            find = False
            for i in range(4):
                temp = rotate(temp)
                if len(set(temp) & set(blank)) == len(temp):
                    find = True
                    break

            if find:
                used[idx2] = True
                answer += len(block)
                break

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges