99클럽 코테 스터디 35일차 TIL, 프로그래머스 / 퍼즐 조각 채우기

🔑 오늘의 학습 키워드 BFS, 구현

🔗 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/84021

 

from collections import deque

def solution(game_board, table):
    answer = 0
    n = len(game_board)
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    def in_range(x, y):
        return 0 <= x < n and 0 <= y < n

    def bfs(board, start_x, start_y, find_value):
        queue = deque([(start_x, start_y)])
        block = []
        board[start_x][start_y] = find_value ^ 1 
        while queue:
            x, y = queue.popleft()
            block.append((x - start_x, y - start_y))  # 상대 좌표 저장
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if in_range(nx, ny) and board[nx][ny] == find_value:
                    board[nx][ny] = find_value ^ 1
                    queue.append((nx, ny))
        return block

    def rotate(block):
        return [(-y, x) for x, y in block]

    def normalize(block):
        min_x = min(x for x, y in block)
        min_y = min(y for x, y in block)
        return sorted((x - min_x, y - min_y) for x, y in block)

    def get_rotations(block):
        rotations = []
        for _ in range(4):
            block = rotate(block)
            normalized_block = normalize(block)
            if normalized_block not in rotations:
                rotations.append(normalized_block)
        return rotations

    def find_blocks(board, value):
        blocks = []
        for i in range(n):
            for j in range(n):
                if board[i][j] == value:
                    block = bfs(board, i, j, value)
                    blocks.append(normalize(block))
        return blocks

    # 게임보드에서 구멍(0) 찾기
    goal_holes = find_blocks(game_board, 0)
    # 테이블에서 블록(1) 찾기
    have_blocks = find_blocks(table, 1)

    for hole in goal_holes:
        hole_rotations = get_rotations(hole)
        for block in have_blocks:
            block_rotations = get_rotations(block)
            if any(h in block_rotations for h in hole_rotations):
                answer += len(block)
                have_blocks.remove(block)
                break

    return answer

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

문제가 요구하는 사항이 많아서 함수단위로 우선 작성을 한다음 코드 세부 구현을 해야겠다고 생각했다.

1. BFS로 구멍이랑 블록을 구분하는 함수를 작성해야겠다고 생각했다.

2. 2개가 반환한 리스트들을 가지고 비교하면서 답을 갱신해 나가면 되겠다고 생각했다.

 

3. 구멍에 딱 맞지 않는 블록은 채워진게 아니었는데 이 문제에서는 회전하는게 좀 문제라고 생각했다.

 

3-1. 회전을 하는 것에 대해 설계 시간을 제일 오래 했는데 해당 블록을 가지고 이어지는 방향을 기록할 것이냐

 

3-2. 회전된 위치를 가져온 다음 0,0 기준으로 정규화 하여 기록할 것이냐 였다.

-> 이 방법으로 해결했다.

⏰ 예상 시간 복잡도 O(N ^ 2 * K ^ 2)

N은 50 , K는 구멍 크기 ( N <= K )

제한 사항

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에는 반드시 하나 이상의 블록이 놓여 있습니다.

😎 알고리즘 개요

1. BFS 탐색 

추후 블록간 비교를 하기 위해서 상대 좌표를 저장했다

예를들면 ) (3,3) , ( 3,4 ) , ( 3,5 ) -> ( 0,0 ), (0, 1) ,( 0, 2 )

 

탐색은 game_board는 구멍 ( 0 )을 찾아야 하고, table은 블록 ( 1 )을 찾아야해서 find_value를 나눠줬다.

directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def in_range(x, y):
    return 0 <= x < n and 0 <= y < n

def bfs(board, start_x, start_y, find_value):
    queue = deque([(start_x, start_y)])
    block = []
    board[start_x][start_y] = find_value ^ 1 
    while queue:
        x, y = queue.popleft()
        block.append((x - start_x, y - start_y))  # 상대 좌표 저장
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if in_range(nx, ny) and board[nx][ny] == find_value:
                board[nx][ny] = find_value ^ 1
                queue.append((nx, ny))
    return block

def find_blocks(board, value):
    blocks = []
    for i in range(n):
        for j in range(n):
            if board[i][j] == value:
                block = bfs(board, i, j, value)
                blocks.append(normalize(block))
    return blocks
    
# 게임보드에서 구멍(0) 찾기
goal_holes = find_blocks(game_board, 0)
# 테이블에서 블록(1) 찾기
have_blocks = find_blocks(table, 1)

 

2. 블록 정규화 및 회전하면서 찾기

정규화 된 블록이 어떻게 회전하는지에 대해 생각을 해보면 

 

( 0 , 1 ) , ( 1 , 1 ) , ( 2 , 1 ) 이런 애들이 있다고 생각을 해보자 (( 0,0 )은 안 넣음 )

==	==
	==
	==

 

이 블록을 반시계 방향으로 돌리면 ( -1, 0 ), ( -1, 1 ) , ( -1  ,2 ) 가 되는 것을 알 수 있다

==	==	==
==

 

이는 좌표 값이 x, y => -y , x로 바뀌는 것을 볼 수 있다. 따라서 이렇게 4번 회전하면서 비교하면 된다.

 

채워야 하는 구멍이 goal_holes 인데 여기 있는 구멍들을 4번 돌리면서 가지고 있는 블록과 비교를 한다.

 

그래서 돌린 구멍에 해당하는 블록이 있으면 블록을 지워버리고 다음 구멍에 대해 또 찾는 로직이다.

def rotate(block):
    return [(-y, x) for x, y in block]

def normalize(block):
    min_x = min(x for x, y in block)
    min_y = min(y for x, y in block)
    return sorted((x - min_x, y - min_y) for x, y in block)

def get_rotations(block):
    rotations = []
    for _ in range(4):
        block = rotate(block)
        normalized_block = normalize(block)
        if normalized_block not in rotations:
            rotations.append(normalized_block)
    return rotations
    
for hole in goal_holes:
    hole_rotations = get_rotations(hole)
    for block in have_blocks:
        block_rotations = get_rotations(block)
        if any(h in block_rotations for h in hole_rotations):
            answer += len(block)
            have_blocks.remove(block)
            break

 

 

 

✅ 오늘의 회고

- 복잡한 구현 문제도 침착하게 잘 해냈다.

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL