Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Challenger] 퍼즐 조각 채우기 (아직 못 품)

[퍼즐 조각 채우기]

• 못 풀었다. 내일 아예 새로운 마음으로(?) 다시 시도해야 겠다.

접근 과정

• 먼저 문제를 다음과 같이 나눴다.
  1. game_board에서 BFS/DFS를 통해 빈 공간의 좌표를 추출하고, table에서 BFS/DFS를 통해 퍼즐 조각의 좌표를 추출한다.
     • 이 때, game_board에서는 0에 대해 탐색하고, table에서는 1에 대해 탐색해야 함에 유의해야 한다.
  2. 비교하기 좋게 상대좌표로 변환한다.
     • 지금 글을 작성하면서 돌아보니 이걸 set으로 관리하면 안 된다.
  3. 퍼즐 조각이든, game_board든 회전시킨 좌표를 추출해 낸 다음, 이 또한 상대좌표로 변환한다.
  4. 하나씩 매칭하면서 세어준다.

지금 코드에서 잘못된 부분

• 연결 요소의 상대좌표를 구하는 함수 cc가 set을 return한다. 빈 칸이든, 퍼즐의 모양이든 중복된 모양이 있을 수 있으므로 set으로 관리하면 안 된다.
• 한 퍼즐의 회전된 정도에 따라 최대 네 가지의 모양이 pieces에 저장되는데, 어떤 빈칸을 채운 퍼즐은 다른 빈 칸에 이용할 수 없어야 하지만 각기 다른 네 모양이 pieces에 남아있으므로 퍼즐이 실제보다 더 많이 저장된다.
• 일단 퍼즐만 돌리는 코드도 만들어 보았고, 사용하고나면 빼주는 것도 만들었었는데 set으로 관리하는 게 문제였던 것 같다. 내일 처음부터 새로운 마음으로 다시 풀어봐야 겠다.
• 제한사항 약하니 set이나 dictionary같은 해시보다, 일단 리스트와 같은 자료구조로 나이브하게 짠 다음 최적화해나가자.

WA.

from collections import deque

def solution(game_board, table):

    def cc(arr, v):
        n = len(arr)
        a = [r[:] for r in arr]

        def bfs(i, j):
            rel_coords = {(0, 0)}
            queue = deque([(i, j)])
            a[i][j] = not v
            delta = ((-1, 0), (1, 0), (0, -1), (0, 1))

            while queue:
                y, x = queue.popleft()
                for dy, dx in delta:
                    ny, nx = y+dy, x+dx
                    if 0<=ny<n and 0<=nx<n and a[ny][nx] == v:
                        a[ny][nx] = not v
                        rel_coords.add((ny-i, nx-j))
                        queue.append((ny, nx))            
            
            return tuple(sorted(rel_coords))

        return {bfs(i, j) for i in range(n) for j in range(n) if a[i][j] == v}
    
    def rotate(arr):
        n = len(arr)        
        ret = [r[:] for r in arr]

        for i in range(n):
            for j in range(n):
                ret[j][n-1-i] = arr[i][j]

        return ret
        
    empty = cc(game_board, 0)
    pieces = cc(table, 1)

    for _ in range(3):
        table = rotate(table)
        pieces.update(cc(table, 1))

    ret = empty&pieces
    return sum(map(len, ret))

---