[Python] 퍼즐 조각 채우기

 

퍼즉 조각 채우기

• 문제 출처: 프로그래머스
• 난이도: level 3
• input size: $n \le 50$ (정사각 격자)
• (주관) 자료구조: 그래프
• (주관) 알고리즘: 완전탐색, BFS
• (주관) 시간복잡도: $O(n^2) = O(V+E)$ ($V=n^2, E=2n(n-1)$)

 

2개의 정사각 배열이 주어진다. 1은 블록 한 조각을, 0은 빈 공간을 나타낸다.

game_board의 빈 공간을 table에 있는 블록을 이용하여 채운다.

하나의 공간을 여러 블록으로 채우거나, 작은 블록으로 큰 빈공간을 채우고 나서도 빈 공간이 있으면 안된다.

이때 채워지는 블록의 면적을 리턴하면 된다.

입출력 예 1#1

STEP 1. 서로 같은 블록

단순히 면적을 구하는 것은 DFS/BFS를 이용하여 구할 수 있다.

그리고 블록은 좌표의 리스트로 나타낼 수 있다.

class Block:
    def __init__(self, pos_list: list):
        self.pos_list = pos_list

 

문제는 블록의 면적이 겹쳐지는 경우를 어떻게 나타낼지 고민을 많이 했다.

내 생각에 'ㅓ' 모양이 가장 표현하기 까다로울 것 같아서 이를 우선적으로 고민했다.

(막대모양은 단순해보여서)

 

game_board의 가운데 'ㅗ'의 좌표와 table의 파란색 'ㅓ'은 서로 일치하는 모양이다.

우선 좌표를 통일할 필요가 있다.

그러면 (정렬된) 리스트를 순회하면서 각 좌표가 같은지만 확인하면 된다.

블록 좌표 정규화 (1)

블록 좌표 정규화 (2)

 

이제 동일한 모양의 블록은 좌표 리스트가 동일하다.

그러나 위 두 블록은 회전을 하면 동일한 블록이지만, 현재는 동일하지 않다.

def set_min(self):
    x_min, y_min = self.pos_list[0]
    for (x, y) in self.pos_list:
        x_min = min(x_min, x)
        y_min = min(y_min, y)
        
    self.x_min = x_min
    self.y_min = y_min

def normalize(self):            
    for i, (x, y) in enumerate(self.pos_list):
        self.pos_list[i] = (x - self.x_min, y - self.y_min)
    self.pos_list.sort()

STEP 2. 블록의 회전

90도 회전을 했을때의 좌표를 구해보자.

좌표의 회전

따라서 새로운 점들의 좌표는 $(x, y) \to (y, -x)$가 된다.

좌표가 바뀌었으므로 위에서 설명한 좌표 정규화를 다시 해야한다.

혹시 선형대수학을 배웠다면, -90도 회전변환을 이용하여 동일한 결과를 얻을 수 있다.

좌표의 회전 예시

def rotate(self):
    for i, (x, y) in enumerate(self.pos_list):
        self.pos_list[i] = (y, -x)
    self.set_min()
    self.normalize()
        
def is_fit(self, other):
    if self.size != other.size:
        return False
        
    is_same = True
    diff_cnt = 0
    for _ in range(4):
        self.rotate()
        for i in range(len(self.pos_list)):
            if self.pos_list[i] != other.pos_list[i]:
                diff_cnt += 1
                break
    is_same = False if diff_cnt == 4 else True
    return is_same

코드

BFS를 2번 수행하여 각각 empty_blocks, table_blocks를 구한다.

두 블럭의 원소끼리 is_fit() 메소드를 이용하여 채워지는지 확인한다.

채워졌다면, 해당 블럭이 채워졌다는 표시(used라는 멤버변수 사용)를 하여 중복집계되지 않게 한다.

from collections import deque

class Block:
    def __init__(self, pos_list: list):
        self.pos_list = pos_list
        self.size = len(self.pos_list)
        self.used = False
        self.x_min = None
        self.y_min = None
        
        self.set_min()
        self.normalize()
        
    def set_min(self):
        x_min, y_min = self.pos_list[0]
        for (x, y) in self.pos_list:
            x_min = min(x_min, x)
            y_min = min(y_min, y)
        
        self.x_min = x_min
        self.y_min = y_min
        
    def normalize(self):            
        for i, (x, y) in enumerate(self.pos_list):
            self.pos_list[i] = (x - self.x_min, y - self.y_min)
        self.pos_list.sort()
            
    def rotate(self):
        for i, (x, y) in enumerate(self.pos_list):
            self.pos_list[i] = (y, -x)
        self.set_min()
        self.normalize()
        
    def is_fit(self, other):
        if self.size != other.size:
            return False
        
        is_same = True
        diff_cnt = 0
        for _ in range(4):
            self.rotate()
            for i in range(len(self.pos_list)):
                if self.pos_list[i] != other.pos_list[i]:
                    diff_cnt += 1
                    break
        is_same = False if diff_cnt == 4 else True
        return is_same
    
def make_block(x0, y0, board, visited, allow_type):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    N, M = len(visited), len(visited[0])
    
    q = deque([(x0, y0)])
    visited[x0][y0] = True
    pos_list = []
    
    while q:
        x, y = q.popleft()
        pos_list.append((x, y))
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            if board[nx][ny] != allow_type:
                continue
            if not visited[nx][ny]:
                q.append((nx, ny))
                visited[nx][ny] = True
                
    return Block(pos_list)

def get_block_bfs(board, allow_type):
    N, M = len(board), len(board[0])
    visited = [[False for _ in range(M)] for _ in range(N)]
    
    blocks = []
    for i in range(N):
        for j in range(M):
            if board[i][j] == allow_type and not visited[i][j]:
                block = make_block(i, j, board, visited, allow_type)
                blocks.append(block)
    return blocks

def solution(game_board, table):    
    empty_blocks = get_block_bfs(game_board, 0)
    table_blocks = get_block_bfs(table, 1)

    # find fittig pairs of blocks
    answer = 0
    for eb in empty_blocks:
        for tb in table_blocks:
            if not eb.used and not tb.used and eb.is_fit(tb):
                answer += eb.size
                eb.used, tb.used = True, True
    
    return answer

 

참고

전체 채점 데이터의 실제 시간과 메모리 사용량이다.

정확성 테스트 결과