🔗
풀이
(1)table의 퍼즐 조각들을 찾아서 (2)game_board의 칸에 하나씩 끼워맞추면 된다. 보통 그래프 탐색은 개수를 세거나 몇 칸 이동해야 하냐 정도의 문제인데 여기서는 그래프 탐색을 통해 퍼즐 조각이 어떤 모양으로 생겼는지(?)를 파악해야 했다.
일단 퍼즐 조각들을 찾아서 딕셔너리 저장한 후, 게임 보드를 돌면서 빈 칸의 모양을 찾고 빈 칸의 모양과 딱 맞는 퍼즐 조각이 있는지를 확인하는 방식으로 풀이했다.
🧩 1. 퍼즐 조각 찾기
table을 dfs로 탐색하면서 이어진 조각들을 찾아 위치 좌표값을 반환했다. 이 위치값들은 그림의 가장 큰 사각형을 기준으로 한 값들로 기준이 되는 값은 가장 왼쪽 위의 (0, 0) 좌표 값이다. 각각의 조각들의 모양을 찾기 위해서 기준을 전체 사각형에서 각 조각에 딱 맞는 빨간색 사각형으로 바꿔준다. 그러기 위해서는 각 빨간색 사각형의 가장 왼쪽 위에 있는 값들로 기준 값들을 변경해야 한다.
아래의 3번 조각은 전체 사각형을 기준으로 했을 때 위치 좌표 값은 (4, 0), (4, 1), (5, 1)의 값을 갖게 된다. 빨간 사각형으로 기준 사각형을 바꾸게 되면 기준값은 (4, 0)이 되고 이 값들을 각각의 위치 좌표 값에서 빼주게 되면 (0, 0), (0, 1), (1, 1)로 기준이 (0, 0)로 바뀐 좌표 값이 반환된다.
이제 빨간 사각형 크기를 갖는 2차원 배열을 선언하고 위의 좌표 값들 위치에 1 값을 넣어주게 되면 아래와 같이 조각의 모양을 구할 수 있다.
# 3번 조각
[
[1, 1],
[0, 1]
]퍼즐 조각 탐색(dfs)
def dfs(arr, i, j, block):
if i<0 or j<0 or i>=len(arr) or j>=len(arr[0]) or [i, j] in block or not arr[i][j]:
return block
arr[i][j] = 0
block.append([i, j])
block = dfs(arr, i-1, j, block)
block = dfs(arr, i+1, j, block)
block = dfs(arr, i, j-1, block)
block = dfs(arr, i, j+1, block)
return block2차원 배열로 만들기
퍼즐 조각의 길이도 같이 반환했다. 결국 구하려는 건 최대 몇 개의 칸을 채울 수 있느냐이기 때문에..
def make_block(block):
row_min, col_min = map(min, zip(*block))
for i in range(len(block)):
block[i][0] -= row_min
block[i][1] -= col_min
row_max, col_max = map(max, zip(*block))
arr = [[0]*(col_max+1) for _ in range(row_max+1)]
for r, c in block:
arr[r][c] = 1
return arr, len(block)🧊 2. 빈 칸 찾기
두 배열을 보면 0과 1이 바뀌기만 했지 사실상 같은 모양이라는 걸 알 수 있다. 위에서 퍼즐 조각을 구했을 때처럼 보드판에서도 빈 칸을 퍼즐 조각이라고 생각하고 구하면 된다. 함수의 재사용을 위해서 보드판의 1과 0을 바꿔준다.
보드판에서 빈 칸의 모양을 찾으면 위에서 저장한 퍼즐 조각들 중에 있는지 확인하고 있다면 해당하는 칸 수를 정답에 더해준다. 없다면 넘어간다.
위에서 퍼즐 조각들에 대해 기준점을 (0, 0)으로 맞출 수 있도록 했기 때문에 여기서도 빈 칸을 찾으면 똑같이 (0, 0)에 맞춰진 채로 나오게 된다. 조각은 회전이 가능하다고 했으며 총 4회까지 회전 가능하므로 4번까지 90도로 회전해서 일치하는 퍼즐조각이 있는지 확인한다.
위의 보라색 1번 조각이 4번 회전하게 되면 아래와 같다.
def puzzle_block(block, cnt):
for _ in range(4):
if blocks[str(block)]:
blocks[str(block)] -= cnt
return cnt
block = rotate(block)
return 0😎 최종 코드
def solution(game_board, table):
answer = 0
# 시계 방향 90도 회전
def rotate(arr):
return list(map(list, zip(*arr[::-1])))
# dfs 그래프 탐색
def dfs(arr, i, j, block):
if i<0 or j<0 or i>=len(arr) or j>=len(arr[0]) or [i, j] in block or not arr[i][j]:
return block
arr[i][j] = 0
block.append([i, j])
block = dfs(arr, i-1, j, block)
block = dfs(arr, i+1, j, block)
block = dfs(arr, i, j-1, block)
block = dfs(arr, i, j+1, block)
return block
# 2차원 배열로 만들기
def make_block(block):
row_min, col_min = map(min, zip(*block))
for i in range(len(block)):
block[i][0] -= row_min
block[i][1] -= col_min
row_max, col_max = map(max, zip(*block))
arr = [[0]*(col_max+1) for _ in range(row_max+1)]
for r, c in block:
arr[r][c] = 1
return arr, len(block)
# 빈 칸에 맞는 퍼즐 조각 찾기
def puzzle_block(block, cnt):
for _ in range(4):
if blocks[str(block)]:
blocks[str(block)] -= cnt
return cnt
block = rotate(block)
return 0
# 퍼즐 조각의 모양이 문자열 형태로 저장됨
# 각 칸의 개수를 값으로 가짐
blocks = defaultdict(int)
for i in range(len(table)):
for j in range(len(table[0])):
if table[i][j]:
block, cnt = make_block(dfs(table, i, j, []))
blocks[f"{block}"] += cnt
game_board = list(map(lambda x: list(map(lambda y: 0 if y else 1,x)) ,game_board))
for i in range(len(game_board)):
for j in range(len(game_board[0])):
if game_board[i][j]:
answer += puzzle_block(*make_block(dfs(game_board, i, j, [])))
return answer
from collections import defaultdict
