[python3] 퍼즐 조각 채우기 lv.3 : 구현

빡센 구현이었습니다... 이거보다 쉽게 풀 수 있는 방법이 있을 것 같은데.. 다른 분들의 코드는 추후에 구경하도록 하겠습니다.

 

아이디어

구현이 복잡한만큼 수도코드를 꼼꼼하게 작성해서 함수를 잘 나눠서 사용할 필요가 있을 것 같습니다. 제가 접근한 단계는 다음과 같습니다.

1. game_board 와 table 에서 각각 블록을 추출하여 배열에 담는다.
   
   • 판에서 dfs를 돌면서 추출한다.
   • game_board는 0을 추출, table 은 1을 추출해야하므로 함수화하면서 추출 숫자를 지정할 수 있게 한다.
   • output :
     • [블룩1, 블록2, ... ]
     • 블록1 = [좌표1, 좌표2, ... ]
2. 블록의 좌표들을 그 블록에 꼭 맞는 가로세로를 가진 직사각형 맵 위에 있는 것 처럼 좌표를 수정한다.
3. table의 블록들을 회전시켜가면서 좌표가 완전히 똑같은 game_board 블록이 있는지 확인해야한다.
   1. table 블록과 크기가 같은 game_board 블록만 골라서 확인하려고 한다. game_board의 블록들을 "key=크기, value=블록정보"의 dict로 바꿔준다.
      • 크기 : [블록1, 블록2, 블록3, ...]
   2. table 블록의 회전 모양새를 만들어줘야한다. 시계방향 90도로 돌렸을때 좌표값이 어떻게 바뀌는지 공식화 한다.
      • (r, c) : 회전 이전 좌표, (nr, nc) : 회전 후 좌표, R : 회전 이전 row 수
      • nr = c
      • nc = (R-1) - r
   3. table 블록과 크기가 같은 game_board 블록들을 하나씩 확인해본다.
   4. game_board 블록과 table 블록의 회전 모양새가 동일한지 확인한다.
      • 모양새가 동일한지 확인하는 방법으로  table 블록의 모든 좌표가 game_board 에 있는지 in 으로 확인한다.
   5. 동일하다면 그 크기만큼 점수를 올리고 game_board 에서 그 블록을 지운다.

 

더 나은 아이디어

3-4 에서 모양새가 동일한지 확인하는 걸 처음엔 set(좌표들) == set(좌표들) 로 시도해보려고 했습니다. 근데 좌표값을 [r,c] 배열로 사용했더니 해싱이 안돼서 set의 원소로 넣을 수가 없더라구요. 그래서 in으로 해결했는데...

왜 안되나 생각을 해보니 배열은 set에 들어간 뒤에 값을 바꿔버릴 수 있기 때문에 해싱이 안되는 것 같더라구요. 그러면 값이 고정되는 튜플은..? 시도해보니 튜플은 set의 원소가 될 수 있었습니다..!

코딩 과정에서 좌표값을 변경해주는 작업이 있었어서 자료구조를 배열로 가져갔는데, 수정이 완료된 뒤에 자료구조를 튜플로 바꿔서 고정시키고 set에 넣은 후 비교하면 for문을 하나 줄일 수 있어서 속도도 빨라지고 코드도 좀 더 간결해질 것 같습니다.

 

고려한 부분 + 새로 알게 된 사실

1. dict의 경우 없는 key를 접근하면 runtime error가 발생합니다. key값이 있는지 확인하는 과정을 거치도록 합시다.

2. 함수에 배열 등의 자료구조를 넘겨주는 경우 함수 안에서 값을 변경하면 input으로 넣은 본체가 수정됩니다. 필요시마다 deepcopy를 적절히 사용해주어야 합니다.

3. 배열은 해싱이 불가능, 튜플은 가능.

 

코드

from copy import deepcopy

def solution(game_board, table):
    
    D = [(-1,0),(1,0),(0,1),(0,-1)] # dfs를 위한 4방향 이동기
    
    def dfs(board,r,c,points,find) :
        if board[r][c] == find :
            points.append([r,c])
            board[r][c] = 2
            for dr,dc in D :
                if r+dr >= 0 and r+dr < len(board) and c+dc >= 0 and c+dc < len(board) :
                    dfs(board,r+dr,c+dc,points,find)
                    
    # 1.
    # find = 유효 블록의 숫자가 0인지 1인지.            
    def find_block(board,find) :
        blocks = []
        for r in range(len(board)) :
            for c in range(len(board[0])) :
                if board[r][c] == find :
                    bp = []
                    dfs(board,r,c,bp,find)
                    blocks.append(bp)
        return blocks
        
    # 2.
    def to_single_block(block) :
        minr, maxr, minc, maxc = 100,0,100,0
        for r,c in block :
            minr = min(minr,r)
            maxr = max(maxr,r)
            minc = min(minc,c)
            maxc = max(maxc,c)
        for i in range(len(block)) :
            block[i][0] -= minr
            block[i][1] -= minc
        R = maxr-minr
        C = maxc-minc
        return R,C,block # R과 C는 rotate을 시킬 때 필요하므로 다시 계산하지 않게 저장해놓는 용도
    
    # 3-2.
    def rotate_single_block(R,C,block) : 
        block = deepcopy(block)
        blocks = [deepcopy(block)]
        for i in range(3) :
            nblock = []
            for r,c in block :
                # nr = c
                # nc = (R-1)-r
                nblock.append([c,R-r])
            blocks.append(deepcopy(nblock))
            block = nblock
            R,C = C,R
        return blocks
    
    # 3-1.
    def to_dict(blocks) :
        diction = {i:[] for i in range(1,7)}
        for b in blocks :
            diction[len(b)].append(b)
        return diction
    
    # game_board 블록들, table 블록들을 원하는 형식에 맞춰서 만들기
    gb_blocks = to_dict([to_single_block(b)[2] for b in find_block(game_board,0)])
    t_blocks = [to_single_block(b) for b in find_block(table,1)]
    
    # table 블록이 game_board 블록과 회전시 일치하지 확인하기
    answer = 0
    for R,C,b in t_blocks :
        brotate = rotate_single_block(R,C,b) # 회전 결과 저장
        for i,gb in enumerate(gb_blocks[len(b)]) : # 크기가 같은 블록들 중에
            flag = 0
            for rb in brotate : # 회전 결과 중에 같은게 있는지 찾는다.
                flag = 0
                for p in rb : # 좌표들이 다 같은지 확인
                    if p in gb :
                        continue
                    else :
                        flag = 1
                        break
                if flag == 0 : # 일치했다면
                    answer += len(b) # 결과에 크기를 더하고
                    del gb_blocks[len(b)][i] # game_board에서는 제외한다.
                    break
            if flag == 0 :
                break
          
    return answer