문제

퍼즐 조각 채우기
1. 게임 보드에는 퍼즐의 홈이 파여있고, 테이블에 퍼즐이 놓여있다.
2. 퍼즐과, 홈은 상/하/좌/우로 인접해있지 않다.
3. 퍼즐의 홈에 정확이 맞는 퍼즐을 맞추어야 한다.
4. 총 몇 칸을 채울 수 있는지 계산한다.

아이디어

핵심 아이디어

1. dfs/bfs를 통한 퍼즐, 퍼즐의 홈 좌표 찾기.
2. 좌표를 이용하여 사각형 모양 퍼즐 만들기
   ex) 좌표 (0, 0), (0, 1), (1, 1), (1, 2)를 구했을 때 만들 사각형 퍼즐
   
3. 하나의 퍼즐을 90도씩 4번 돌려 만들 수 있는 퍼즐 만들기.
4. 퍼즐을 홈에 맞추기.

풀이 아이디어

1. 좌표 찾기
   1) bfs/dfs를 통해 퍼즐의 좌표를 저장한다.
   2) 퍼즐의 좌표의 기준을 (0, 0)으로 변경한다.
   3) 기준을 변경하기 위해 퍼즐 좌표 row, col의 최솟값을 찾는다.
   4) 모든 퍼즐 좌표에 최솟값을 뺀다.
2. 좌표로 퍼즐 만들기
   1) 좌표들을 모두 확인하여row, col의 최댓값을 찾는다.
   2) 각 최댓값을 크기로 하는 2차원 배열을 만든다.
   3) 새로만든 배열의 값을 퍼즐 좌표에 맞춰 변경한다.
3. 퍼즐 회전하기
   1) 2차원 배열 A가 있을 때zip(*A[::-1])을 하여 반복문을 통해 순회하면 90도 회전시킬 수 있다.

코드

import copy
from collections import deque, Counter

N = 0
MAX = 9999
dr, dc = (-1, 1, 0, 0), (0, 0, -1, 1)  # 상 하 좌 우


def find_position(r, c, board, visit, val):
    bfs = deque()
    bfs.append([r, c])
    r_min, c_min = MAX, MAX
    pos = []

    while len(bfs) != 0:
        r, c = bfs.popleft()  # 실제 좌표
        r_min, c_min = min(r_min, r), min(c_min, c)
        visit[r][c] = True
        pos.append([r, c])
        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                if board[nr][nc] == val and visit[nr][nc] is False:
                    bfs.append([nr, nc])
	# shift 과정.
    for i in range(len(pos)):
        pos[i][0] -= r_min
        pos[i][1] -= c_min
    return pos


def make_piece(pos):
    r_max, c_max = 0, 0
    for p in pos:
        r_max, c_max = max(p[0], r_max), max(p[1], c_max)
    r, c = r_max, c_max
    piece = [[0 for _ in range(c + 1)] for _ in range(r + 1)]
    for p in pos:
        piece[p[0]][p[1]] = 1
    return piece


def get_piece(r, c, board, visit, val):
    pos = find_position(r, c, board, visit, val)
    piece = make_piece(pos)
    return piece


def rotate(pattern):
    new_pattern = []
    for p in zip(*pattern[::-1]):
        new_pattern.append(list(p))
    return new_pattern


def get_pattern_size(pattern):
    return sum(sum(p) for p in pattern)


def fill_pattern(pattern, puzzles):
    for puzzle in puzzles:
        p = puzzle
        for i in range(4):
            p = rotate(p)
            if pattern == p:
                cnt = get_pattern_size(pattern)
                puzzles.remove(puzzle)
                return cnt
    return 0


def solution(game_board, table):
    global N
    N = len(game_board)
    visit_b = [[False for _ in range(N)] for _ in range(N)]
    visit_t = [[False for _ in range(N)] for _ in range(N)]
    patterns = []
    puzzles = []

    for r in range(N):
        for c in range(N):
            if visit_b[r][c] is False and game_board[r][c] == 0: # 방문하지 않았고 벽이 채워 넣을 수 있으면
                patterns.append(get_piece(r, c, game_board, visit_b, 0))
            if visit_t[r][c] is False and table[r][c] == 1:
                puzzles.append(get_piece(r, c, table, visit_t, 1))
            visit_b[r][c], visit_t[r][c] = True, True

    answer = 0
    for pattern in patterns:
        answer += fill_pattern(pattern, puzzles)

    return answer