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

1. 문제

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

코딩테스트 연습 - 3주차

2. 접근 방법

완전 빡! 구현입니다,,~!

이걸 어째야하나 하다가 승환님의 풀이를 듣고 츄롸이츄롸이

 

1. game_board를 순회해서 빈 공간을 찾아 해당 부분만 똑 떼어서 리스트에 담습니다. -> board_lst

2. table을 순회해서 조각이 존재하는 공간을 찾아 해당 부분을 똑 떼어서 리스트에 담습니다. -> block_lst

참고로 찾는 과정은 bfs를 사용했습니다

3. 찾은 후 board_lst를 하나씩 순회하며 해당 보드에 맞는 block을 찾아줍니다.

이 때, block을 회전 시켜봅니다. (90도, 180도, 270도)

 

여튼 무튼 회전을 시켜보고 맞으면 answer를 갱신하고 고런 식으로 문제를 풀이했습니다.

 

로직자체는 어렵지 않지만 구현하는 데 꽤 까다로운 문제였습니다~!

3. 코드

Python

from collections import deque

def solution(game_board, table):
    def check_table():
        nonlocal table
        _blocks = []
        for y in range(N):
            for x in range(N):
                if table[y][x] == 1:
                    items, table = bfs(x, y, table, 1)
                    _blocks.append(items)
        return _blocks

    def check_game_board():
        nonlocal game_board
        _blocks = []
        for y in range(N):
            for x in range(N):
                if game_board[y][x] == 0:
                    items, game_board = bfs(x, y, game_board, 0)
                    _blocks.append(items)
        return _blocks

    def make_block(blocks, _type):
        _blocks = []
        for block in blocks:
            x_lst = [x for x, y in block]
            y_lst = [y for x, y in block]
            min_x, max_x = min(x_lst), max(x_lst)
            min_y, max_y = min(y_lst), max(y_lst)
            block.sort(key=lambda x: (x[1], x[0]))
            new_block = [[0 if _type == 'block' else 1] * (max_x-min_x+1) for _ in range(max_y-min_y+1)]
            for item in block:
                _x, _y = item[0]-min_x, item[1]-min_y
                new_block[_y][_x] = 1 if _type == 'block' else 0
            _blocks.append(new_block)
        return _blocks

    def rotate_block(block):
        rotate_blocks_lst = [block]
        for _ in range(3):
            block = rotate(block)
            rotate_blocks_lst.append(block)
        return rotate_blocks_lst

    def is_fit(board, block):
        BOARD_X_LEN = len(board[0])
        BOARD_Y_LEN = len(board)
        _block_lst = rotate_block(block)
        for _block in _block_lst:
            block_x_len = len(_block[0])
            block_y_len = len(_block)
            is_fit_flag = True
            if BOARD_X_LEN == block_x_len and BOARD_Y_LEN == block_y_len:
                for y in range(BOARD_Y_LEN):
                    _sum = [board[y][x] + _block[y][x] for x in range(BOARD_X_LEN)]
                    if _sum != [1] * BOARD_X_LEN:
                        is_fit_flag = False
                        break
                if is_fit_flag:
                    return True
        return False

    def rotate(block):
        x_len = len(block[0])
        y_len = len(block)
        new_block = [[0] * y_len for _ in range(x_len)]
        for y in range(y_len):
            for x in range(x_len):
                if block[y][x] == 1:
                    new_block[x][y_len-y-1] = 1
        return new_block

    def is_board(x, y):
        if 0 <= x < N and 0 <= y < N:
            return True
        return False

    def bfs(x, y, board, type):
        q = deque()
        q.append((x, y))
        dx = (1, -1, 0, 0)
        dy = (0, 0, 1, -1)
        items = []

        while q:
            x, y = q.popleft()
            items.append((x, y))
            board[y][x] = -1
            for i in range(4):
                tx, ty = x + dx[i], y + dy[i]
                if is_board(tx, ty) and board[ty][tx] == type:
                    q.append((tx, ty))
        return items, board

    def get_board_score(_board):
        score = 0
        for y in range(len(_board)):
            for x in range(len(_board[0])):
                if board[y][x] == 0:
                    score += 1
        return score
    answer = 0
    N = len(table)
    _table = check_table()
    _game_board = check_game_board()
    block_lst = make_block(_table, 'block')
    board_lst = make_block(_game_board, 'board')
    block_visited = [False] * len(block_lst)
    for board in board_lst:
        for i in range(len(block_lst)):
            if block_visited[i]:
                continue
            block = block_lst[i]
            if is_fit(board, block):
                block_visited[i] = True
                answer += get_board_score(board)
                break
    return answer

4. 마치며

위클리 1, 2주차는 넘 이지였는데,

갑자기 swea스러운 문제 두두등장

 

참고한 testcase는 여기있습니다요

https://programmers.co.kr/questions/19906

프로그래머스