[프로그래머스 Lv. 3] 퍼즐 조각 채우기

문제

https://programmers.co.kr/learn/courses/30/lessons/84021

접근

BFS를 이용한 구현 문제

1) bfs를 이용해 game_board, table 조각의 좌표를 저장한다. 저장할 때 좌표의 비교를 위해 정렬해서 저장한다.

2) 저장한 좌표들을 (0,0)을 기준으로 평행이동 시킨다.

3) 각각의 좌표를 비교한다. 두 좌표가 일치할 시 일치된 table 좌표를 지워주고 answer에 값을 더해준다. 일치하지 않을 시 game_board 좌표를 90도로 돌려주면서 비교를 해주고 다시 일치하는지 비교한다.

Code

import copy
from collections import defaultdict, deque

def solution(game_board, table):
    game_coodi, table_coodi = [], []
    dx,dy = [1,0,-1,0], [0,1,0,-1]
    answer=0
    def get_coodi(coodi):
        ret=[]
        miny, minx = 10000, 10000
        for y, x in coodi:
            miny, minx = min(y, miny), min(x, minx)

        for y,x in coodi:
            ret.append((y-miny, x-minx))
        return ret

    def bfs(y,x, board, check):
        q = deque()
        board[y][x]=2
        ret = []
        ret.append((y,x))
        q.append((y,x))

        while q:
            y,x = q.popleft()

            for i in range(4):
                cx = x + dx[i]
                cy = y + dy[i]
                if cx < 0 or cx >= len(board[0]) or cy < 0 or cy >= len(board):
                    continue

                if board[cy][cx] == check:
                    board[cy][cx]=2
                    q.append((cy,cx))
                    ret.append((cy,cx))

        return sorted(ret)

    def rotation(block):
        n = len(game_board)
        ret = []
        for b in block:
            ret.append((b[1], n - 1 - b[0]))
        return sorted(get_coodi(ret))

    for y in range(len(game_board)):
        for x in range(len(game_board[0])):
            if not game_board[y][x]:
                game_coodi.append(bfs(y,x,game_board,0))

            if table[y][x] == 1:
                table_coodi.append(bfs(y,x,table, 1))

    game_standard_coodi, table_standard_coodi = [],[]
    for g in game_coodi:
        game_standard_coodi.append(get_coodi(g))

    for t in table_coodi:
        table_standard_coodi.append(get_coodi(t))

    for g_coodi in game_standard_coodi:
        if g_coodi in table_standard_coodi:
            answer+=len(g_coodi)
            table_standard_coodi.remove(g_coodi)
        else:
            flag=False
            for t_coodi in table_standard_coodi:
                tmp = copy.deepcopy(t_coodi)
                for l in range(4):
                    if tmp == g_coodi:
                        answer+=len(g_coodi)
                        table_standard_coodi.remove(t_coodi)
                        flag=True
                        break
                    else:
                        tmp = rotation(tmp)
                if flag:
                    break
    return answer

여담

이런 문제가 가장 어려운 것 같다. 파이썬인데도 코드가 80줄이 넘어가다니 ㅠ 빡센 구현 문제는 적응이 너무 힘들다...