문제 링크

풀이 과정

• 시뮬레이션 문제는 큰 문제를 세부 문제로 분할하는 것이 유리한 것 같습니다.
  • 특정 풀이 방법이 있는 것이 아니라, 문제 조건마다 구현해야 할 기능이 다르기 때문입니다.
  • 또한, 런타임 에러 또는 오답을 맞이하였을 때 어디서 실수를 하였는지 인지하기 쉽습니다.
• 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 된다고 했습니다.
  • 따라서, 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

유사 문제

• 혼자서 하는 틱택토