[프로그래머스] 퍼즐 조각 채우기

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/84021

 

2. 코드

python 1

from collections import deque

def bfs(x, y, visited, board, target):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True
    shape = [(x, y)]

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

    while queue:
        cx, cy = queue.popleft()
        for dx, dy in directions:
            nx, ny = cx+dx, cy+dy
            if 0<=nx<len(board) and 0<=ny<len(board) and not visited[nx][ny] and board[nx][ny] == target:
                visited[nx][ny] = True
                queue.append((nx, ny))
                shape.append((nx, ny))
    return shape

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

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

def extract_shapes(board, target):
    visited = [[False]*len(board) for _ in range(len(board))]
    shapes = []
    for i in range(len(board)):
        for j in range(len(board)):
            if not visited[i][j] and board[i][j] == target:
                shape = bfs(i, j, visited, board, target)
                shapes.append(normalize(shape))
    return shapes

def match_puzzle(empty, puzzle_shapes, used):
    for i, puzzle in enumerate(puzzle_shapes):
        if used[i]:
            continue
        rotated = puzzle
        for _ in range(4):
            rotated = rotate(rotated)
            if normalize(rotated) == empty:
                used[i] = True
                return len(empty)
    return 0

def solution(game_board, table):
    empty_spaces = extract_shapes(game_board, 0)
    puzzle_shapes = extract_shapes(table, 1)
    used = [False] * len(puzzle_shapes)
    answer = 0

    for empty in empty_spaces:
        answer += match_puzzle(empty, puzzle_shapes, used)

    return answer

아이디어

• game_board의 0들은 퍼즐이 들어갈 빈 공간.
• table의 1들은 실제 퍼즐 조각.
• 퍼즐 조각을 회전시켜서(90, 180, 270 도 각각 확인) 빈 공간과 모양이 맞으면 끼워 넣을 수 있음.
• 좌표는 실제 위치와 무관하고, 모양이 일치하는지만 보면 됨.
• 이를 위해 모든 모양은 정규화(normalization) 해서 비교함.

풀이

1. bfs( ) 함수
   • game_board나 table에서 모양(조각)을 찾아주는 함수
   • visited 배열을 사용해서 이미 확인한 위치는 다시 확인 안 하게 함 (중복 방지)
   • 시작 좌표부터 queue에 넣고, 상하좌우 탐색하면서 같은 값(0 또는 1)인 좌표를 shape에 저장
   • shape에는 연결된 좌표들이 담김 → 하나의 퍼즐 조각이나 빈칸 모양
2. normalize( ) 함수
   • bfs로 찾은 좌표 리스트는 실제 위치 기준(ex. (3,2), (4,2))이라, 위치는 다르지만 모양은 같을 수 있음
   • 그래서 좌표 중 가장 작은 x, y 값을 0으로 만들고 → 나머지도 상대적으로 옮김
   • 정렬해서 비교할 수 있게 정리함
   • → 결국 (0,0)을 기준으로 모양만 남기기
3. rotate( ) 함수
   • 문제 조건에 뒤집기는 안 되지만 회전은 가능하다고 했음
   • 퍼즐을 90도 돌리기 위해 (x, y) → (y, -x) 형태로 바꿈
   • 4번 돌리면 0도, 90도, 180도, 270도 다 확인 가능함
4. extract_shapes( ) 함수
   • game_board나 table에서 각각 모양들 추출하는 함수
   • game_board는 0인 부분을 찾아야 하고
   • table은 1인 부분을 찾아야 함
   • bfs 호출해서 shape 추출하고, normalize로 정리해서 담음
5. match_puzzle(empty, puzzle_shapes)

• 하나의 빈칸 모양 (empty)에 대해 사용하지 않은 퍼즐 조각들과 비교
• 90도씩 4번 회전하며 비교, 동일하면 해당 인덱스 반환

1. solution(game_board, table)

• game_board에서 0으로 된 빈칸 모양을 추출
• table에서 1로 된 퍼즐 모양을 추출
• 하나씩 매칭하며 사용한 퍼즐은 used로 체크
• 퍼즐이 맞으면 해당 칸 수만큼 누적해서 answer 증가

 

3. 메모

• 큰 틀에서 문제 해결 방안은 이해함(아이디어에 있는 내용)
• 실제로 어떻게 구현해야 할지 다소 어려웠음
• 검색을 통한 참조로 문제풀음
• BFS/DFS를 활용한 덩어리 탐색, normalize 개념, 좌표 회전 방식을 학습함
• 좌표 비교에서는 절대 위치가 아닌 상대 위치(0,0 기준)가 핵심임
• 회전 후에도 normalize를 다시 해줘야 비교가 정확해진다는 걸 놓쳐 초반에 오류 발생
• 유사 문제에 적용 가능한 패턴 정리: 모양 추출 → 정규화 → 회전 → 비교