---

프로그래머스 위클리 챌린지 3주차 “퍼즐 조각 채우기” 문제를 풀어보았습니다.

여기를 누르면 설명을 건너뛸 수 있습니다.

---

문제 설명

테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.

• 조각은 한 번에 하나씩 채워 넣습니다.
• 조각을 회전시킬 수 있습니다.
• 조각을 뒤집을 수는 없습니다.
• 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.

다음은 퍼즐 조각을 채우는 예시입니다.

위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.

이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.

• 3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.
• 5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.

다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.

최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있습니다.

현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 3 ≤ game_board의 행 길이 ≤ 50
• game_board의 각 열 길이 = game_board의 행 길이
  • 즉, 게임 보드는 정사각 격자 모양입니다.
  • game_board의 모든 원소는 0 또는 1입니다.
  • 0은 빈칸, 1은 이미 채워진 칸을 나타냅니다.
  • 퍼즐 조각이 놓일 빈칸은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
• table의 행 길이 = game_board의 행 길이
• table의 각 열 길이 = table의 행 길이
  • 즉, 테이블은 game_board와 같은 크기의 정사각 격자 모양입니다.
  • table의 모든 원소는 0 또는 1입니다.
  • 0은 빈칸, 1은 조각이 놓인 칸을 나타냅니다.
  • 퍼즐 조각은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
• game_board에는 반드시 하나 이상의 빈칸이 있습니다.
• table에는 반드시 하나 이상의 블록이 놓여 있습니다.

---

입출력 예

game_board	table	result
[[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]]	[[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]]	14
[[0,0,0],[1,1,0],[1,1,1]]	[[1,1,1],[1,0,0],[0,0,0]]	0

---

입출력 예 설명

입출력 예 #1

입력은 다음과 같은 형태이며, 문제의 예시와 같습니다.

입출력 예 #2

블록의 회전은 가능하지만, 뒤집을 수는 없습니다.

---

Solution

[문제 이해]

• board와 table에서 블록 or 빈 공간의 좌표를 얻어야함
• 얻은 좌표들을 끼리끼리 모아두기
• 빈 공간에 블록을 돌려가며 비교
  → 블록 회전 기능이 필요
• 결과는 채워진 공간의 합

이번 문제는 한 눈에 봐도 난이도가 꽤 되는 문제였습니다.

하지만 코딩 테스트가 얼마 남지 않은 기념?으로 검색을 하지 않고 문제 풀이에 도전했습니다.

이해한 내용을 바탕으로 코드를 작성했습니다.

[코드]

from collections import deque, defaultdict
import numpy as np

def solution(game_board, table):
    # ↓, →, ↑, ← 이동 좌표
    step = ((1, 0), (0, 1), (-1, 0), (0, -1))

    # 보드에서 n이 있는 위치를 구함
    def getLoc(boards, n=1):
        n_arr = list()
        for x, board in enumerate(boards):
            [n_arr.append((x, y)) for y in list(np.where(np.array(board)==n)[0])]
        return n_arr

    # loc 배열을 조합
    def combineLoc(locs):
        nonlocal step
        loc_dict = defaultdict(list)
        dq = deque()
        dq.append(locs[0])
        count = 1
        loc_dict[count].append((locs[0][0], locs[0][1]))
        del locs[0]

        while dq:
            x, y = dq.popleft()
            for moveX, moveY in step:
                newX = x + moveX
                newY = y + moveY
                if (newX, newY) in locs:
                    loc_dict[count].append((newX, newY))
                    dq.appendleft((newX, newY))
                    del locs[locs.index((newX, newY))]
            else:
                if not dq and len(locs) != 0:
                    dq.append(locs[0])
                    count += 1
                    loc_dict[count].append((locs[0][0], locs[0][1]))
                    del locs[0]
        return loc_dict

    # 리스트 회전 함수
    # -> numpy.rot90() 똑같은 기능의 함수 (풀고 검색해봄)
    def rotation(block):
        block = np.array(list(zip(*block[::-1])))
        return block.tolist()

    # 불필요한 0 라인 제거, 같은 모양에도 불구하고 0 라인 때문에 틀림
    # -> 이 부분 때문에 테스트가 계속 실패하여 마지막에 추가함, 풀이 2일 걸린 원흉
    def removeZero(arr):
        temp = []
        for i, a in enumerate(arr):
            if sum(a) == 0:
                temp.append(i)
        else:
            if len(temp) == 0:
                arr = rotation(arr)
                for i, a in enumerate(arr):
                    if sum(a) == 0:
                        temp.append(i)
        while temp != []:
            del arr[temp[-1]]
            del temp[-1]

        return arr
    
    def getFrame(leng):
        return [[0] * leng for _ in range(leng)]

    # 모양 비교를 위해 블록과 빈 공간 구분없이 1로 통일하여 프레임에 배치
    def setFrame(block):
        # 2개 리스트로 분할
        list_x, list_y = zip(*block)
        min_x, max_x, min_y, max_y = min(list_x), max(list_x), min(list_y), max(list_y)
        _x = max_x - min_x
        _y = max_y - min_y
        # 프레임 길이
        leng = (_x if _x > _y else _y) + 1
        arr = getFrame(leng)
        for x, y in block:
            arr[x-min_x][y-min_y] = 1

        arr = removeZero(arr)

        return arr

    # 빈 공간과 블록 모양 비교
    def scanShape(empty, block, n=3):
        # 빈 공간
        empty_arr = setFrame(empty)
        # 블록
        block_arr = setFrame(block)

        leng = len(block_arr)
        if leng != len(empty_arr):
            return False
        if empty_arr == block_arr:
            return True

        # 블록 회전하며 확인, n=1 -> 시계 방향으로 90도 회전
        for _ in range(n):
            block_arr = rotation(block_arr)
            if empty_arr == block_arr:
                return True

        return False

    def scanMap(game_board, table):
        count = 0
        dq = deque()
        # 빈 공간 좌표 list (무작위 상태)
        empty_loc = getLoc(game_board, 0)
        # 블록 좌표 list (무작위 상태)
        block_loc = getLoc(table)

        # 빈 공간 좌표 dict (공간별 정리)
        empty_comb = combineLoc(empty_loc)
        # 블록 좌표 dict (블록별 정리)
        block_comb = combineLoc(block_loc)

        dq.append(list(empty_comb.keys())[0])

        # 빈 공간에 블록을 비교
        # 일치하면 공간과 블록 제거해가며 비교
        while dq:
            e_k = dq.popleft()
            for b_k in block_comb:
                if scanShape(empty_comb[e_k], block_comb[b_k]):
                    count += len(block_comb[b_k])
                    if len(empty_comb) >= 1:
                        del empty_comb[e_k]
                        del block_comb[b_k]
                        if len(empty_comb) != 0:
                            dq.append(list(empty_comb.keys())[0])
                    break
            else:
                if len(empty_comb) >= 1:
                    del empty_comb[e_k]
                    if len(empty_comb) != 0:
                        dq.append(list(empty_comb.keys())[0])

        return count

    answer = scanMap(game_board, table)
    return answer

[여담]

우선은 통과한 것에 의의를 두었습니다.

풀이 방식을 프레임을 두고 블록과 빈 공간을 올려서 비교하는 방법을 사용했는데 프레임의 빈 공간 차이로 실패했습니다. → 이 부분을 찾지 못해서 풀이 시간이 굉장히 오래걸렸습니다.

검색없이 구현을 하다보니 잘 정리가 되지 않았지만 정리하는 습관을 들일 수 있도록 노력을 좀 해야할 것 같습니다.

다른 사람의 풀이 중에 기억에 남는 풀이가 2개 있었습니다.

1. 풀이 방식은 비슷하지만 dataclass 를 사용해서 데이터를 클래스로 관리한 코드
   (제 코드와 방식이 비슷해서 처리 시간은 2번에 비해 느리다)
2. 처리 시간 효율 끝판왕
   (제 코드는 가장 오래걸린 처리 시간이 695ms 인데 2번 코드는 9ms입니다…)

if scanShape() 같은 실수를 하지 않았으면 좋았을 것 같다.
오늘도 배운다.

[1번 코드]

from collections import Counter
from dataclasses import dataclass
from itertools import product

@dataclass(frozen=True)
class Pos:
    x: int
    y: int

    def neighbors(self):
        return [
            Pos(self.x, self.y - 1),
            Pos(self.x + 1, self.y),
            Pos(self.x, self.y + 1),
            Pos(self.x - 1, self.y),
        ]

def make_tile_from_positions(positions):
    """Smallest possible representation with rotation"""

    def rotate90(tile):
        return tuple(
            tuple(tile[i][j] for i in range(len(tile)))
            for j in reversed(range(len(tile[0])))
        )

    positions = set(positions)

    xs = [pos.x for pos in positions]
    min_x = min(xs)
    max_x = max(xs)

    ys = [pos.y for pos in positions]
    min_y = min(ys)
    max_y = max(ys)

    tile_representations = [
        tuple(
            tuple(Pos(i, j) in positions for j in range(min_y, max_y + 1))
            for i in range(min_x, max_x + 1)
        )
    ]

    for __ in range(3):
        tile_representations.append(rotate90(tile_representations[-1]))

    return min(tile_representations)

def get_tile_size(tile):
    return sum(sum(row) for row in tile)

def parse_tiles(board, tile_value=1):
    n = len(board)

    # Add sentinel boundaries
    sentinel = 1 - tile_value

    board = [
        [sentinel] * (n + 2),
        *([sentinel] + row + [sentinel] for row in board),
        [sentinel] * (n + 2),
    ]

    # Detect tiles
    tile_positions = []
    for i, j in product(range(1, n + 1), range(1, n + 1)):
        if board[i][j] == tile_value:
            stack = [Pos(i, j)]
            squares = []
            while stack:
                curr = stack.pop()
                board[curr.x][curr.y] = sentinel
                squares.append(curr)
                for neighbor in curr.neighbors():
                    if board[neighbor.x][neighbor.y] == tile_value:
                        stack.append(neighbor)
            tile_positions.append(squares)

    # Make tiles
    tiles = [make_tile_from_positions(p) for p in tile_positions]

    return tiles

def solution(game_board, table):
    tiles = parse_tiles(table, 1)
    empty_spaces = parse_tiles(game_board, 0)

    tile_counter = Counter(tiles)
    empty_space_counter = Counter(empty_spaces)

    used_tiles = tile_counter & empty_space_counter

    return sum(get_tile_size(tile) * occ for tile, occ in used_tiles.items())

[2번 코드]

def dfs(table, i, j, shape, find = 1):
        # 우 좌 하 상
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0] 
    stack = [[i, j]] # 현재 위치 스택에 저장
    shape.append((i, j))
    
    while stack:
        a, b = stack.pop()
        table[a][b] = -1 # 방문 처리
        for i in range(4): # 우 좌 하 상 순으로 스택에 저장 -> 상 하 좌 우 순으로 꺼내져 수행된다.
            x = a + dx[i]
            y = b + dy[i]
            if 0 <= x < len(table) and 0 <= y < len(table[0]) and table[x][y] == find:
                table[x][y] = -1
                stack.append([x, y])
                shape.append((x, y))
                
# 블록이나 빈 칸을 (0, 0)을 시작점으로 옮김
def rearrange(shape):
    minX = min([x[1] for x in shape])
    minY = min([x[0] for x in shape])
    shape = [(s[0]-minY, s[1]-minX) for s in shape]
    return sorted(shape) # 블록이 여러 칸으로 이루어진 경우 같은 모양에서 같은 결과를 위해 정렬해서 반환

# 여러 방향으로 회전 후 하나의 값 반환
def rotate(shape):
    if len(shape) == 1: return shape
    shapes = []
    shape = list(shape)
    shape.sort()
    width = max([x[1] for x in shape]) - min([x[1] for x in shape])
    height = max([x[0] for x in shape]) - min([x[0] for x in shape])
    # 시계 방향으로 4회 회전
    for _ in range(4):
        tmp = []
        # 시계 방향으로 회전하는 방법
        # 1. (x, y) 값을 (y, x)로 x, y를 맞바꾸는 '전치'
        for pos in shape:
            tmp.append((pos[1], pos[0])) # 전치
        # 2. 전치된 결과에서 x 좌표를 가로 길이에서 뺀다.
        tmp = [(x[0], width - x[1]) for x in tmp]
        tmp = rearrange(tmp) # 재정렬
        shape = tmp # 시계 방향으로 회전 한 블록을 shape에 다시 저장
        shapes.append(shape)
        width, height = height, width # 2x3 크기의 블록이 회전하면 3x2가 되므로 width, height를 맞바꾼다.
    
    # 4번 회전한 결과가 담긴 shapes의 최소값을 반환하면 
    # 같은 구성의 순서가 다른 리스트에서도 항상 동일한 결과 반환
    return min(shapes) 
                
def solution(game_board, table):
    # table에서 추출된 블록들과 game_board에서 추출된 빈 칸들을 저장하는 리스트
    shapes, spaces = list(), list() 
    # game_board와 table의 크기가 같다고 주어졌기 때문에 한 번에 돌릴 수 있음
    for i in range(len(table[0])):
        for j in range(len(table)):
            # table에서 블록 추출하는 dfs
            if table[i][j] == 1: # 1이면 블록
                shape = list()
                dfs(table, i, j, shape) # table에서 블록(1) 추출
                shape = rearrange(shape) # 추출한 블록 (0, 0) 부터 시작하도록 위치 값 조정
                shape = rotate(shape) # 회전 후 항상 동일한 결과 반환
                shapes.append(shape) # shapes 에서 블록들 관리
            # game_board에서 빈 칸 추출하는 dfs
            if game_board[i][j] == 0: # 0이면 빈 칸
                space = list()
                dfs(game_board, i, j, space, find = 0) # game_board에서 빈 칸(0) 추출
                space = rearrange(space) # 추출한 공백 (0, 0) 부터 시작하도록 위치 값 조정
                space = rotate(space) # 회전 후 항상 동일한 결과 반환
                spaces.append(space) # spaces 에서 공백들 관리
                
    answer = 0
    for space in spaces:
        for shape in shapes:
            if space == shape: # 같은 모양이 있다면
                answer += len(shape) # 블록의 개수만큼 더한다
                shapes.remove(shape) # 사용된 블록은 제거
                break
    return answer