[프로그래머스] 퍼즐조각 채우기 (Python, BFS, 구현)

🌱 문제

BFS/DFS 문제이지만 개인적으로 BFS 찔끔 쓰고, 완전 빡쎈 구현인 것 같았던.. 문제입니다.

프로그래머스

 

 

 

🌱 풀이

1. game_board의 빈 공간과 table의 퍼즐 정보를 저장

우선, game_board에서 빈공간과 table에서 퍼즐들의 정보를 알아야 합니다. 즉, game_board에서는 0의 위치, table에서는 1의 위치를 알아야합니다. game_board의 인접한 0들은 하나의 퍼즐이 들어갈 수 있는 하나의 빈공간으로 취급하고, table에서 인접한 1은 하나의 퍼즐이므로 BFS 알고리즘을 사용하여 정보를 저장합니다.

같은 BFS 알고리즘을 game_board와 table로 두 번 써야 하기 때문에 함수화 하였고, 이때 game_board에서는 0의 위치를 table에서는 1의 위치를 알아야 하므로 find_block() 함수에서 f 인자를 받아 XOR(^) 연사자와 함께 함수 내부에서 0와 1로 변환하여 알맞게 사용하였습니다.

from collections import deque

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def find_block(board, f):
    empty_board_list = []
    visited = [[False] * len(board[0]) for _ in range(len(board))]

    for i in range(len(board)):
        for j in range(len(board[i])):
            if not visited[i][j] and board[i][j] == f:
                queue = deque([(i, j)])
                board[i][j] = f ^ 1
                visited[i][j] = True
                lst = [(i, j)]

                while queue:
                    x, y = queue.popleft()
                    for _ in range(4):
                        nx, ny = x + dx[_], y + dy[_]
                        if nx < 0 or nx > len(board) - 1 or ny < 0 or ny > len(board) - 1:
                            continue
                        elif board[nx][ny] == f:
                            queue.append((nx, ny))
                            board[nx][ny] = f ^ 1
                            visited[nx][ny] = True
                            lst.append((nx, ny))
                empty_board_list.append(lst)

    return empty_board_list

 

아래의 game_board와 table 정보를 find_block() 함수에 넣으면 아래와 같이 블록들의 정보가 담깁니다.

game_board = [
    [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]
]

table = [
    [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]
]

empty_blocks = find_block(game_board, 0)
# [[(0, 2), (0, 3), (1, 3), (2, 3), (2, 4)], [(0, 5), (1, 5)], [(1, 0), (1, 1), (2, 0)], [(3, 2), (4, 2), (4, 1), (4, 3)], [(4, 5), (5, 5), (5, 4)], [(5, 0)]]

puzzles = find_block(table, 1)
# [[(0, 0), (1, 0)], [(0, 3), (0, 4), (1, 4), (2, 4), (2, 5)], [(1, 2), (2, 2), (2, 1), (3, 2)], [(4, 0), (4, 1), (5, 1)], [(4, 3), (4, 4)]]

 

2. 인덱스 정보로 2차원 리스트 만들기

인덱스 정보로 table 모양, 즉 2차원 리스트 형태로 만들 차례입니다. 예를 들면, 아래와 같이 앞서 find_blocks() 함수에서 찾은 [(0, 2), (0, 3), (1, 3), (2, 3), (2, 4)] 정보를 아래와 같은 2차원 리스트 형태로 만드는 것입니다.

저는 make_table()라는 함수로 만들어주었고 코드는 아래와 같습니다.

def make_table(block):
    x, y = zip(*block)
    c, r = max(x) - min(x) + 1, max(y) - min(y) + 1
    table = [[0] * r for _ in range(c)]

    for i, j in block:
        i, j = i - min(x), j - min(y)
        table[i][j] = 1
    return table

 

3. 2차원 리스트를 회전하는 함수

이 문제에서 중요한 함수입니다. 퍼즐은 90도씩 회전하면서 빈칸을 채울 수 있기 때문에 위에서 만든 퍼즐의 2차원 리스트를 90도씩 회전해보면서 빈칸과 일치하는지 확인해야 합니다. 따라서 2차원 리스트를 오른쪽으로 90도씩 회전하는 rotate() 함수를 만들었습니다. 이때, 문제에서 퍼즐로 채운 빈칸의 개수를 물어보기 때문에 rotate함수에서 퍼즐의 크기, 즉 2차원 리스트에서 1의 개수도 함께 카운트하여 리턴해줍니다

def rotate(puzzle):
    rotate = [[0] * len(puzzle) for _ in range(len(puzzle[0]))]
    count = 0
    for i in range(len(puzzle)):
        for j in range(len(puzzle[i])):
            if puzzle[i][j] == 1:
                count += 1
            rotate[j][len(puzzle) - 1 - i] = puzzle[i][j]
    return rotate, count

 

이제 solution 함수에서 위에서 적절히 구현해 놓은 함수를 사용하여 정답을 리턴해보겠습니다. 

def solution(game_board, table):
    answer = 0
    empty_blocks = find_block(game_board, 0)
    puzzles = find_block(table, 1)

    for empty in empty_blocks:
        filled = False
        table = make_table(empty)

        for puzzle_origin in puzzles:
            if filled == True:
                break

            puzzle = make_table(puzzle_origin)
            for i in range(4):
                puzzle, count = rotate(puzzle)

                if table == puzzle:
                    answer += count
                    puzzles.remove(puzzle_origin)
                    filled = True
                    break

• empty_blocks, puzzles에 빈공간과 퍼즐 정보를 저장합니다.
• 빈공간을 하나씩 돌면서 2차원 리스트로 만들고(make_table()) 
• 빈공간에 대해서 puzzle들을 하나씩 돌면서 마찬가지로 2차원 리스트로 만들고 4번 회전 시키면서 빈공간의 모양과 퍼즐의 모양이 일치하는지 확인합니다. (두 개의 2차원 리스트(table(빈공간)와 puzzle(퍼즐))이 일치하는지 확인)
• filled 변수는 해당 빈공간이 이미 채워졌는지를 확인하는 변수로, filled가 True이면 puzzle을 확인하지 않습니다.
• puzzles.remove(puzzle_origin)으로 퍼즐을 빈공간에 채웠을 때 puzzles에서 제거하여 다음 빈공간에서 중복되어 채워지지 않도록 합니다.

 

 

 

🌱 정답 코드

# !/usr/bin/env python
# -*- coding: utf-8 -*-
# programmers 퍼즐조각채우기

from collections import deque

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]


# board와 puzzle의 각각 빈공간과 블럭을 찾는 함수 (BFS)
def find_block(board, f):
    empty_board_list = []
    visited = [[False] * len(board[0]) for _ in range(len(board))]

    for i in range(len(board)):
        for j in range(len(board[i])):
            if not visited[i][j] and board[i][j] == f:
                queue = deque([(i, j)])
                board[i][j] = f ^ 1
                visited[i][j] = True
                lst = [(i, j)]

                while queue:
                    x, y = queue.popleft()
                    for _ in range(4):
                        nx, ny = x + dx[_], y + dy[_]
                        if nx < 0 or nx > len(board) - 1 or ny < 0 or ny > len(board) - 1:
                            continue
                        elif board[nx][ny] == f:
                            queue.append((nx, ny))
                            board[nx][ny] = f ^ 1
                            visited[nx][ny] = True
                            lst.append((nx, ny))
                empty_board_list.append(lst)

    return empty_board_list


# block의 인덱스들로 table을 만드는 함수
def make_table(block):
    x, y = zip(*block)
    c, r = max(x) - min(x) + 1, max(y) - min(y) + 1
    table = [[0] * r for _ in range(c)]

    for i, j in block:
        i, j = i - min(x), j - min(y)
        table[i][j] = 1
    return table


# 오른쪽으로 90도 회전하는 함수
def rotate(puzzle):
    rotate = [[0] * len(puzzle) for _ in range(len(puzzle[0]))]
    count = 0
    for i in range(len(puzzle)):
        for j in range(len(puzzle[i])):
            if puzzle[i][j] == 1:
                count += 1
            rotate[j][len(puzzle) - 1 - i] = puzzle[i][j]
    return rotate, count


def solution(game_board, table):
    answer = 0
    empty_blocks = find_block(game_board, 0)
    puzzles = find_block(table, 1)

    for empty in empty_blocks:
        filled = False
        table = make_table(empty)

        for puzzle_origin in puzzles:
            if filled == True:
                break

            puzzle = make_table(puzzle_origin)
            for i in range(4):
                puzzle, count = rotate(puzzle)

                if table == puzzle:
                    answer += count
                    puzzles.remove(puzzle_origin)
                    filled = True
                    break

    return answer