문제 링크
풀이 과정
•
시뮬레이션 문제는 큰 문제를 세부 문제로 분할하는 것이 유리한 것 같습니다.
◦
특정 풀이 방법이 있는 것이 아니라, 문제 조건마다 구현해야 할 기능이 다르기 때문입니다.
◦
또한, 런타임 에러 또는 오답을 맞이하였을 때 어디서 실수를 하였는지 인지하기 쉽습니다.
•
게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 된다고 했습니다.
◦
따라서, game_board 의 빈 공간(0)을 채우려면, 딱 알맞은 사이즈의 퍼즐 조각이 있어야 합니다.
•
이 사실을 바탕으로 문제를 해결해봅시다!
•
궁극적인 목표는 game_board 의 빈 공간(0)과 모양이 동일한 table 의 퍼즐 조각(1)을 찾는 것입니다.
•
이는 다음과 같이 해결할 수 있습니다.
◦
1) game_board 에서 빈 공간 블록과 table 에서 퍼즐 조각 블록을 먼저 찾습니다.
◦
2) 빈 공간 블록과 퍼즐 조각 블록의 비교를 위해, 각 블록을 직사각형 형태로 변환합니다 → 행렬 값을 비교해야 하므로
◦
3) 두 직사각형을 회전 시키면서, 모양이 완벽하게 일치하는 지 확인합니다.
구현 팁
•
각 단계를 하나의 기능(함수) 단위로 구현합니다.
•
game_board 에서 빈 공간 블록과 table 에서 퍼즐 조각 블록을 찾는 logic은 완벽하게 동일합니다.
◦
다만, 빈 공간 블록은 0에 해당하는 값이고, 퍼즐 조각 블록은 1에 해당하는 값을 찾습니다.
◦
따라서, 하나의 함수를 선언하고 플래그를 추가함으로써, 로직을 통일시킬 수 있습니다.
▪
빈 공간을 봐야하는 지, 퍼즐 조각 블록을 봐야하는 지
▪
플래그는 XOR 연산을 통해 구현할 수 있습니다!
•
경험 상, 행렬의 대칭/회전 연산은 빈번하게 출제되는 것 같습니다. 이번 기회에 익숙해질 수 있어 아주 좋았습니다.
전체 코드
from collections import deque
def isin_boundary(cur_row, cur_col, rows, cols):
row_cond = (cur_row >= 0 and cur_row < rows)
col_cond = (cur_col >= 0 and cur_col < cols)
return row_cond & col_cond
def find_blocks(board, mode):
# mode: 0 -> table / mode: 1 -> game_board
row_len, col_len = len(board), len(board[0])
visited_list = [[0 for _ in range(col_len)] for _ in range(row_len)]
deltas = [(-1, 0), (1, 0), (0, -1), (0, 1)]
blocks = list()
for row in range(row_len):
for col in range(col_len):
if (board[row][col] ^ mode == 1) and (visited_list[row][col] == 0):
block_temp = [(row, col)]
visited_list[row][col] = 1
queue = deque([(row, col)])
while queue: # BFS
cur_row, cur_col = queue.popleft()
for dy, dx in deltas:
nrow, ncol = cur_row + dy, cur_col + dx
if isin_boundary(nrow, ncol, row_len, col_len):
if (visited_list[nrow][ncol] == 0) and (board[nrow][ncol] ^ mode == 1):
visited_list[nrow][ncol] = 1
block_temp.append((nrow, ncol))
queue.append((nrow, ncol))
blocks.append(block_temp)
return blocks
def make_rectangle(blocks):
rows, cols = zip(*blocks)
row_max, row_min = max(rows), min(rows)
col_max, col_min = max(cols), min(cols)
row_len = row_max - row_min + 1
col_len = col_max - col_min + 1
rectangle = [[0 for _ in range(col_len)] for _ in range(row_len)]
for row, col in blocks:
rectangle[row-row_min][col-col_min] = 1
return rectangle
def rotate(rectangle): # 90도 회전
row_len, col_len = len(rectangle), len(rectangle[0])
result = [[0 for _ in range(row_len)] for _ in range(col_len)]
blocks = 0
for row in range(row_len):
for col in range(col_len):
if rectangle[row][col] == 1: blocks += 1
result[col][row_len-1-row] = rectangle[row][col]
return (result, blocks)
def solution(game_board, table):
answer = 0
game_board_blocks = find_blocks(game_board, 1)
table_blocks = find_blocks(table, 0)
for game_board_block in game_board_blocks:
find_flag = False
game_rectangle = make_rectangle(game_board_block)
for table_block in table_blocks:
if find_flag: break
table_rantangle = make_rectangle(table_block)
for _ in range(4): # 최대 360도 회전
game_rectangle, blocks = rotate(game_rectangle)
if game_rectangle == table_rantangle:
find_flag = True
answer += blocks
table_blocks.remove(table_block)
break
return answer
Python
복사