[코딩테스트/Python] 프로그래머스 "퍼즐 조각 채우기"

📍 문제 출처

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

프로그래머스

 

📍 풀이 방법

• 테이블 위의 퍼즐 조각을 찾아 게임보드의 빈칸에 맞춰 넣는 문제이다.
• 처음에는 퍼즐 조각을 어떻게 회전해야 할지 몰라 테이블 자체를 회전하려고 했다. 이 경우 회전된 테이블 위의 퍼즐을 매번 찾아야 해서 비효율적이었다.
• find_groups 메소드는 주어진 보드를 순서대로 순회하며 특정한 값을 따라 너비 우선 탐색을 한다. 이를 통해 게임 보드의 빈칸 (value=0) 과 테이블의 퍼즐 조각 (value=1) 을 찾을 수 있었다.
• 빈칸 모음과 퍼즐 조각 모음을 하나씩 비교해보면서 (1) 리스트 길이가 동일하고 (2) 그대로, 혹은 회전했을 때 모양이 맞는다면, 빈칸에 맞는 퍼즐을 찾았다고 보았다.

from collections import deque


def find_groups(board, value, N):
    queue = deque()
    dr, dc = [1, 0, -1, 0], [0, 1, 0, -1]
    visited = set()
    groups = []
    for r in range(N):
        for c in range(N):
            if board[r][c] == value and (r, c) not in visited:
                queue.append((r, c))
                group = []
                while len(queue) > 0:
                    cr, cc = queue.popleft()
                    if (cr, cc) in visited:
                        continue
                    visited.add((cr, cc))
                    group.append((cr, cc))
                    for d in range(4):
                        nr, nc = cr + dr[d], cc + dc[d]
                        if 0 <= nr < N and 0 <= nc < N and board[nr][nc] == value:
                            queue.append((nr, nc))
                minr = min(gr for gr, _ in group)
                minc = min(gc for _, gc in group)
                group = [(gr - minr, gc - minc) for gr, gc in group]
                groups.append(group)
                queue.clear()
    return groups

def rotate_group(group):
    maxr = max(gr for gr, _ in group)
    return [(gc, maxr - gr) for gr, gc in group]

def solution(gameboard, table):
    N = len(gameboard)
    blanks = find_groups(gameboard, 0, N)
    puzzles = find_groups(table, 1, N)
    used = [False for _ in puzzles]
    answer = 0
    for blank in blanks:
        blank.sort()
        for i, puzzle in enumerate(puzzles):
            if used[i] or len(blank) != len(puzzle):
                continue
            flag = False
            for j in range(4):
                if j > 0:
                    puzzle = rotate_group(puzzle)
                puzzle.sort()
                if blank == puzzle:
                    answer += len(blank)
                    flag = True
                    used[i] = True
                    break
            if flag:
                break
    return answer