문제 설명
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 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에는 반드시 하나 이상의 블록이 놓여 있습니다.
<코드>
from collections import deque
# 상하좌우 이동을 위한 벡터
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def rotate_90(piece):
return [list(reversed(col)) for col in zip(*piece)]
def get_pieces(board, target):
n = len(board)
visited = [[False] * n for _ in range(n)]
pieces = []
def bfs(x, y):
queue = deque([(x, y)])
visited[x][y] = True
blocks = [(x, y)]
min_x, max_x = x, x
min_y, max_y = y, y
while queue:
cx, cy = queue.popleft()
for i in range(4):
nx, ny = cx + dx[i], cy + dy[i]
if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and board[nx][ny] == target:
visited[nx][ny] = True
queue.append((nx, ny))
blocks.append((nx, ny))
min_x, max_x = min(min_x, nx), max(max_x, nx)
min_y, max_y = min(min_y, ny), max(max_y, ny)
piece = [[0] * (max_y - min_y + 1) for _ in range(max_x - min_x + 1)]
for bx, by in blocks:
piece[bx - min_x][by - min_y] = 1
return piece
for i in range(n):
for j in range(n):
if board[i][j] == target and not visited[i][j]:
pieces.append(bfs(i, j))
return pieces
def can_fit(board_piece, table_piece):
if len(board_piece) != len(table_piece) or len(board_piece[0]) != len(table_piece[0]):
return False
return all(board_piece[i][j] == table_piece[i][j] for i in range(len(board_piece)) for j in range(len(board_piece[0])))
def solution(game_board, table):
empty_spaces = get_pieces(game_board, 0)
puzzle_pieces = get_pieces(table, 1)
used = [False] * len(puzzle_pieces)
answer = 0
for space in empty_spaces:
for i, piece in enumerate(puzzle_pieces):
if used[i]:
continue
for _ in range(4):
if can_fit(space, piece):
answer += sum(sum(row) for row in piece)
used[i] = True
break
piece = rotate_90(piece)
if used[i]:
break
return answer
<풀이과정>
1. 방향 벡터 정의
- dx와 dy는 상하좌우로 이동하기 위한 벡터로, BFS(너비 우선 탐색)에서 인접한 칸을 탐색하는 데 사용
2. 조각 회전 함수 (rotate_90)
- 퍼즐 조각을 90도 회전시키는 함수
3. 퍼즐 조각 추출 함수 (get_pieces)
- 게임 보드 또는 테이블에서 특정 값(빈 공간 또는 퍼즐 조각)에 해당하는 연결된 블록들을 추출하는 함수
- BFS를 사용해 연결된 블록들을 찾아 하나의 퍼즐 조각으로 저장
4. 조각 비교 함수 (can_fit)
- 게임 보드의 빈 공간과 테이블의 퍼즐 조각이 동일한지 비교하는 함수
- 크기가 동일하고 각 요소가 모두 일치하면 True 반환
5. 메인 함수 (solution)
- get_pieces 함수를 통해 게임 보드의 빈 공간과 테이블의 퍼즐 조각들을 각각 추출
- 각 빈 공간에 대해 테이블의 퍼즐 조각을 회전시키면서 맞출 수 있는지 확인하고, 맞는 조각이 있으면 그 조각을 게임 보드에 채우기
'2024 코딩테스트 스터디' 카테고리의 다른 글
[13주_2일차] 프로그래머스-정수 삼각형(Python) (0) | 2024.08.28 |
---|---|
[13주_1일차] 프로그래머스-N으로 표현(Python) (0) | 2024.08.27 |
[12주_6일차] 프로그래머스-여행경로(Python) (0) | 2024.08.25 |
[12주_5일차] 프로그래머스-아이템 줍기(Python) (0) | 2024.08.25 |
[12주_4일차] 프로그래머스-단어 변환(Python) (0) | 2024.08.23 |