[Python] 프로그래머스 (위클리 챌린지 3주차) 퍼즐 조각 채우기

문제 설명
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.

• 조각은 한 번에 하나씩 채워 넣습니다.
• 조각을 회전시킬 수 있습니다.
• 조각을 뒤집을 수는 없습니다.
• 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.

다음은 퍼즐 조각을 채우는 예시입니다.

위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.
이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.

• 3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.
• 5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.

다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.

최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있습니다.
현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 3 ≤ game_board의 행 길이 ≤ 50
• game_board의 각 열 길이 = game_board의 행 길이
  • 즉, 게임 보드는 정사각 격자 모양입니다.
  • game_board의 모든 원소는 0 또는 1입니다.
  • 0은 빈칸, 1은 이미 채워진 칸을 나타냅니다.
  • 퍼즐 조각이 놓일 빈칸은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
• table의 행 길이 = game_board의 행 길이
• table의 각 열 길이 = table의 행 길이
  • 즉, 테이블은 game_board와 같은 크기의 정사각 격자 모양입니다.
  • table의 모든 원소는 0 또는 1입니다.
  • 0은 빈칸, 1은 조각이 놓인 칸을 나타냅니다.
  • 퍼즐 조각은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
• game_board에는 반드시 하나 이상의 빈칸이 있습니다.
• table에는 반드시 하나 이상의 블록이 놓여 있습니다.

---

입출력 예

game_board	table	result
[[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]]	[[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]]	14
[[0,0,0],[1,1,0],[1,1,1]]	[[1,1,1],[1,0,0],[0,0,0]]	0

---

입출력 예 설명
입출력 예 #1
입력은 다음과 같은 형태이며, 문제의 예시와 같습니다.

입출력 예 #2
블록의 회전은 가능하지만, 뒤집을 수는 없습니다.

---

문제풀이

• BFS를 사용하여 game_board와 table에서 각각 도형을 찾아낸다. gamebfs, tablebfs함수가 그 역할
  • game_board의 경우 행렬의 0이 들있는 부분이 도형이 들어가야할 자리이므로 0인 경우를 찾는다.
  • table은 1이 도형을 나타내는 자리미으로 1인 경우를 찾는다.
• 찾은 도형을 행렬(0,0)에 가깝게 붙여준다. (두 테이블에서 나온 도형이 같은 그림인지 알기위함.) format00함수
• game_board에서 나온 도형과 table에서 나온 도형을 90도 씩 돌려 같다면 정답리스트(ans)에 추가한다.
  • 만약 이미 퍼즐조각이 game_board에 들어갔다면 game_board의 flag를 True로 바꾸어준다.

from collections import deque
import copy

game_board = [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]]

table = [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]]

def solution(game_board, table):
    moves = [(-1,0), (1,0), (0,-1), (0,1)]  # 상, 하, 좌, 우

    gameResult = []
    visited = [[0 for col in range(len(game_board))] for row in range(len(game_board))]
    gameResult = gamebfs(gameResult, game_board, moves, visited)

    tableResult = []
    visited = [[0 for col in range(len(table))] for row in range(len(table))]
    tableResult = tablebfs(tableResult, table, moves, visited)

    j=0
    shape = []  #정리된 게임판에 맞춰야할 퍼즐 조각
    for i in range(len(gameResult)):
        if gameResult[i] == 'SPACE':
            shape.append(gameResult[j:i])
            j = i+1

    j=0
    tableshape = [] # 정리된 테이블 퍼즐 조각
    for i in range(len(tableResult)):
        if tableResult[i] == 'SPACE':
            tableshape.append(tableResult[j:i])
            j = i+1

    formattedGameShape = []
    for i in shape:
        formattedGameShape.append(format00(i, table))

    formattedTableShape = []
    for i in tableshape:
        formattedTableShape.append(format00(i, table))

    ans = []
    gameflag = [False]*len(formattedGameShape)

    for i in range(len(formattedGameShape)):
        if formattedGameShape[i] in formattedTableShape and gameflag[i] == False:
            gameflag[i] = True
            formattedTableShape.remove(formattedGameShape[i])
            ans.append(formattedGameShape[i])
        elif gameflag[i] == False:
            tmp_shape = copy.deepcopy(formattedGameShape[i])
            for _ in range(4):
                tmp_shape = rotate90(tmp_shape,table)
                if tmp_shape in formattedTableShape and gameflag[i] == False:
                    gameflag[i] = True
                    formattedTableShape.remove(tmp_shape)
                    ans.append(formattedGameShape[i])
                    break

    fillCount = 0

    for i in ans:
        fillCount += len(i)

    return fillCount

def gamebfs(gameResult,game_board, moves, visited):
    deq = deque()
    for i in range(len(game_board)):
        for j in range(len(game_board)):
            if game_board[i][j] == 0 and visited[i][j] == 0:
                deq.append((i,j))
                visited[i][j] = 1
                while deq:
                    tx, ty = deq.popleft()
                    gameResult.append((tx,ty))
                    for mx, my in moves:
                        if 0 <= tx+mx < len(game_board) and 0 <= ty+my < len(game_board):
                            if game_board[tx+mx][ty+my] == 0 and visited[tx+mx][ty+my] == 0:
                                deq.append((tx+mx, ty+my))
                                visited[tx+mx][ty+my] = 1
                gameResult.append(('SPACE'))

    return gameResult

def tablebfs(tableResult, table, moves, visited):
    deq = deque()
    for i in range(len(table)):
        for j in range(len(table)):
            if table[i][j] == 1 and visited[i][j] == 0:
                deq.append((i,j))
                visited[i][j] = 1
                while deq:
                    tx, ty = deq.popleft()
                    tableResult.append((tx,ty))
                    for mx, my in moves:
                        if 0 <= tx+mx < len(table) and 0 <= ty+my < len(table):
                            if table[tx+mx][ty+my] == 1 and visited[tx+mx][ty+my] == 0:
                                deq.append((tx+mx, ty+my))
                                visited[tx+mx][ty+my] = 1
                tableResult.append(('SPACE'))

    return tableResult

# 도형의 시작위치를 동일하게 만들기 위한 함수
def format00(shape,table):
    temp = []
    min_x = len(table)
    min_y = len(table)
    for i in shape:
        min_x = min(min_x, i[0])
        min_y = min(min_y, i[1])

    for x, y in shape:
        temp.append((x-min_x, y-min_y))
    return sorted(temp)

# 도형을 90도씩 돌리는 경우
def rotate90(shape,table):
    temp = []
    n = len(table)
    for i in shape:
        temp.append((i[1], (n-1-i[0])))
    return sorted(format00(temp,table))

print(solution(game_board, table))

---

매우 오래걸린 문제였다. bfs를 board내에서 다 돌린 함수를 구현하느라 쓸데없이 사용된 중복된 코드가 꽤 많고 수정도 힘들었다.