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

사용 언어 - Python3

문제 - 퍼즐 조각 채우기

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

프로그래머스

 

정답

큐, BFS

채워야할 빈칸과 도형을 분할해서 생각하기

1. def find_board(board,f)

empty_blocks = find_block(game_board,0) # game_board의 빈공간(0) 위치 찾기

puzzles = find_block(table,1) #  table의 블럭(1) 위치 찾기

방문하지 않았고 해당 위치가 f값이라면,

방문처리를 하고 1은 0으로 0은 1로 바꿔줘야 한다.

f ^ 1 (XOR 연산 = 둘중 하나만 참이면 참)

0 1 => 1

1 1 => 0

 

2. def make_table(block)

block의 인덱스 위치들로 table 형태 만들기

총 table의 사이즈는 (max(y) - min(y) + 1) * (max(x) - min(x) + 1)

인덱스 위치를 table[i][j] = 1로 채우기

예) '+' 모양이면 이런 형태로!

0 1 0

1 1 1

0 1 0

 

3. def rotate(puzzle)

오른쪽으로 90도 회전하는 함수

puzzle[i][j]가 1이라면, 1의 개수(채워넣은 칸의 개수, 정답구해야하기 때문)를 카운트한다. count += 1

90도 회전 = (x,y) -> (y,len(puzzle)-1-x)

회전시킨 rotate 모양이 table과 같은지 확인한다.

 

4. def solution(game_board, table)

정답 도출!!!!

먼저 find_block()함수를 통해 채워야할 빈칸과 도형들의 위치 인덱스를 뽑아준다.

채워야할 빈칸의 위치를 확인하면서, 그 위치를 make_table()함수를 통해 table 형태로 만든다.

도형의 위치를 확인하면서, 그 위치를 make_table()함수를 통해 table 형태로 만든다.

rotate()함수를 통해 해당 table을 90도씩 4번 회전하면서 완벽히 맞아떨어지는지 확인한다. 완벽히 들어간다면, 해당 블록 크기를 answer에 합쳐주고, 그 도형은 삭제해준다.

이를 모든 채워야할 빈칸과 남은 도형들로 확인해준다.

 

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

 

 

 

레퍼런스

https://eunbin00.tistory.com/190

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