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

문제

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

코딩테스트 연습 - 퍼즐 조각 채우기

풀이

문제 풀이 방식을 간단하게 표현하면 아래와 같다.

1. table에서 모든 퍼즐조각을 찾는다.

2. game_board에서 모든 퍼즐구멍을 찾는다.

3. table에서 찾은 퍼즐조각과 game_board에서 찾은 퍼즐구멍을 비교한다.

퍼즐조각을 0º, 90º, 180º, 270º로 회전하여 구멍과 비교한다.

같은 퍼즐조각을 여러 퍼즐구멍에 사용하거나

한 퍼즐구멍을 여러 퍼즐조각으로 채우지 않도록 중복체크를 해야 한다. (여기서 시간이 오래 걸렸다)

퍼즐조각 찾기

• 퍼즐을 찾는다 (find item)

table을 차례로 훑어가면서, 퍼즐을 발견하면 (if table[i][j]==1) table과 같은 크기의 item에 퍼즐의 형태를 저장한다.

1. 현재 위치를 item에 저장하고, table에서 해당 위치를 메운다

2. 현재 위치의 →, ←, ↓, ↑가 퍼즐조각인지 체크한다.

2-1. 퍼즐조각이라면 stack에 저장한다.

• item에 비어있는 행과 열을 지운다. (resizing)
• 퍼즐구멍을 찾는 것도 같은 방식으로 해결할 수 있다.

퍼즐조각과 퍼즐구멍 비교하기

1. 퍼즐조각을 0º, 90º, 180º, 270º로 회전한다.

2. 퍼즐조각과  퍼즐구멍을 비교한다.

• isSame()함수

퍼즐조각==퍼즐구멍으로 연산하면, 몇몇 경우에서는 올바른 값을 얻을 수 없었다. 

그래서 isSame()함수를 만들어 type, 행수, 열수, 각 위치의 수를 비교했다.

def isSame(a, b) :
    if type(a)!=type(b) : return False
    if len(a)!=len(b) : return False
    if len(a[0])!=len(b[0]) : return False
    for i in range(len(a)) : 
        for j in range(len(a[0])) : 
            if a[i][j]!=b[i][j] : return False
    return True

• 중복체크

매칭된 퍼즐구멍은 메워서 중복을 막을 필요가 있었다. 그래서 해당 퍼즐구멍을 리스트에서 지웠다.

del blankes[bi] # delete game item

코드

def seek(table, puzzle) : 
    size = len(table)
    itemList = list()
    
    for i in range(size) :
        for j in range(size) :
            if table[i][j]==puzzle : 
                
                # find item
                item = [[0 for c in range(size)] for r in range(size)]
                shape = [i, i, j, j] # max_r, min_r, max_c, min_c
                stack = [(i, j)] # r, c
                
                while stack : 
                    r, c = stack.pop()
                    shape = [max(shape[0], r), min(shape[1], r), max(shape[2], c), min(shape[3], c)] # item resize
                    item[r][c] = 1 # save (r, c)
                    table[r][c] = puzzle+1 # check passed
                    
                    for nr, nc in [(r, c+1), (r, c-1), (r+1, c), (r-1, c)] : # →, ←, ↓, ↑
                        if 0<=nr<size and 0<=nc<size : 
                            if table[nr][nc]==puzzle : 
                                stack.append((nr, nc))
                
                # resizing  
                rx, rn, cx, cn = shape
                item = [[item[r][c] for c in range(cn, cx+1)] for r in range(rn, rx+1)]
                
                itemList.append(item)
    return itemList

def isSame(a, b) :
    if type(a)!=type(b) : return False
    if len(a)!=len(b) : return False
    if len(a[0])!=len(b[0]) : return False
    for i in range(len(a)) : 
        for j in range(len(a[0])) : 
            if a[i][j]!=b[i][j] : return False
    return True  

def match(puzzle, blank) : 
    puzzleShape = (len(puzzle), len(puzzle[0]))
    blankShape = (len(blank), len(blank[0]))
    if sorted(puzzleShape)!=sorted(blankShape) : return 0 # check shape
    
    for i in range(4) : 
        if isSame(puzzle, blank) :
            return sum([sum(row) for row in puzzle])
        puzzle = [row[::-1] for row in zip(*puzzle)]
    return 0
    
def solution(game, table) :  
    puzzles = seek(game, 0)
    blankes = seek(table, 1)
    answer = 0
    
    for pi, puzzle in enumerate(puzzles) :         
        for bi, blank in enumerate(blankes) : 
            temp = match(puzzle,blank)
            if temp>0 :   
                answer += temp
                del blankes[bi] # delete game item
                break
    
    return answer