[프로그래머스] 퍼즐 조각 채우기 - 파이썬(python)

문제 설명

테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 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에는 반드시 하나 이상의 블록이 놓여 있습니다.

 

입출력 예

[[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

블록의 회전은 가능하지만, 뒤집을 수는 없습니다.

 

 

 

나의 풀이

def dfs(i, j, n, k, table, group) :
    if i < 0 or i >= n or j < 0 or j >= n :
        return
    if table[i][j] == k :
        table[i][j] = 1-k
        group.append([i,j])
        dfs(i-1, j, n, k, table, group)
        dfs(i+1, j, n, k, table, group)
        dfs(i, j-1, n, k, table, group)
        dfs(i, j+1, n, k, table, group)
    
    
def spin(board) :
    n = len(board) # 행 길이
    m = len(board[0]) # 열 길이
    result = [[0] * n for _ in range(m)] # 90도 회전한 결과는 행과 열이 반대됨
    for i in range(n):
        for j in range(m):
            result[j][n - 1 - i] = board[i][j]
    return result
    
    
def solution(game_board, table):
    n = len(table)
    
    # table 에 있는 블럭 찾기
    blocks = []
    for i in range(n) :
        for j in range(n) :
            if table[i][j] == 1 :
                group = []
                dfs(i, j, n, 1, table, group)
                min_x = min(group, key=lambda x:x[0])[0]
                min_y = min(group, key=lambda x:x[1])[1]
                
                for k in range(len(group)) :
                    group[k][0] -= min_x
                    group[k][1] -= min_y
                
                max_x = max(group, key=lambda x:x[0])[0] + 1
                max_y = max(group, key=lambda x:x[1])[1] + 1
                
                matrix = [[0] * max_y for _ in range(max_x)]

                for x,y in group :
                    matrix[x][y] = 1

                blocks.append(matrix)
    
    
    # game_board 에 있는 비어있는 모양 찾기
    empty_board = []
    for i in range(n) :
        for j in range(n) :
            if game_board[i][j] == 0 :
                group = []
                dfs(i, j, n, 0, game_board, group)
                min_x = min(group, key=lambda x:x[0])[0]
                min_y = min(group, key=lambda x:x[1])[1]

                for k in range(len(group)) :
                    group[k][0] -= min_x
                    group[k][1] -= min_y
                
                max_x = max(group, key=lambda x:x[0])[0] + 1
                max_y = max(group, key=lambda x:x[1])[1] + 1
                
                
                matrix = [[0] * max_y for _ in range(max_x)]

                for x,y in group :
                    matrix[x][y] = 1
                
                empty_board.append(matrix)
    
#     print(blocks,"\n")
#     print(empty_board, "\n")
    
    answer = 0
    for i in blocks :
        for shape in empty_board :
            if len(i)*len(i[0]) == len(shape)*len(shape[0]) :
                # print("블럭 : {}, 비어있는 틀 : {}".format(i, shape))
                block = i
                find = False
                for _ in range(4) :
                    if block == shape :
                        # print("블럭 : {}, 비어있는 틀 : {} 이 같음".format(block, shape))
                        for c in block :
                            answer += c.count(1)
                        shape[0][0] = -1 # 이미 블럭을 끼웠으므로 -1 을 넣어 다른 블럭이 오지 못하게 함
                        find = True
                        break
                    else :
                        block = spin(block)
                #         print("회전한 블럭 : {}".format(block))
                # print("\n")
                if find : break
                
    
    return answer

으악... 진짜 어렵다 ㅠㅡㅠ 한 3~4시간 푼 것 같은 기분이다..

다행히 시간 제한이 없나보다... 엄청 삽질한 기분인데 ..ㅎㅎ 어찌됐던 통과다!

 

 

 

Step 1

def dfs(i, j, n, k, table, group) :
    if i < 0 or i >= n or j < 0 or j >= n :
        return
    if table[i][j] == k :
        table[i][j] = 1-k
        group.append([i,j])
        dfs(i-1, j, n, k, table, group)
        dfs(i+1, j, n, k, table, group)
        dfs(i, j-1, n, k, table, group)
        dfs(i, j+1, n, k, table, group)

• dfs 로 game_board 에서 비어있는 틀 모양(0으로 이어진 것) / table 에서 1로 이어진 블럭들의 좌표를 찾고, 리턴해주는 함수이다.
• i, j 는 시작하는 좌표를 뜻한다.
• n은 테이블의 길이
• k 는 0일때 블럭으로 판별할 것인지 1일 때 블럭으로 판별할 것인지를 나타내는 기준이다. k는 game_board 와 table 에서 각각 0과 1 이다.

 

Step 2

n = len(table)
    
    # table 에 있는 블럭 찾기
    blocks = []
    for i in range(n) :
        for j in range(n) :
            if table[i][j] == 1 :
                group = []
                dfs(i, j, n, 1, table, group)
                min_x = min(group, key=lambda x:x[0])[0]
                min_y = min(group, key=lambda x:x[1])[1]
                
                for k in range(len(group)) :
                    group[k][0] -= min_x
                    group[k][1] -= min_y
                
                max_x = max(group, key=lambda x:x[0])[0] + 1
                max_y = max(group, key=lambda x:x[1])[1] + 1
                
                matrix = [[0] * max_y for _ in range(max_x)]

                for x,y in group :
                    matrix[x][y] = 1

                blocks.append(matrix)

• 만약, table의 i,j 번째 좌표의 값이 1이라면 이는 하나의 블럭 속 좌표임을 뜻한다. 따라서 해당 좌표에서 시작하여 연결된 나머지 좌표들을 찾기 위해 DFS 를 진행한다.
• 이때, DFS 가 종료되고 블럭을 구성하고 있는 좌표 리스트를 리턴해줄 것이다.
• 나중에 game_board 의 비어있는 모양과 더 쉽게 비교하기 위해, 좌표 리스트를 0 부터 시작하도록 만들어 줄것이며, 사각형으로 만든 후 해당 좌표에만 1, 비어있는 곳은 0으로 채울것이다.
• 즉, 왼쪽에서 노란색 블럭을 구성하는 좌표들을 찾은 후, 오른쪽과 같이 (0,0) 부터 시작하는 새로운 직사각형 형태로 저장한다는 것이다.
• -> [[1,1,0],[0,1,0],[0,1,1]] 이 될 것이다.

• table 의 모든 블럭에 대해 이와 같은 과정을 진행하며, 마찬가지로 game_board 에 0으로 비어있는 공간에 대해서도 위의 과정을 진행한다.
• 이때 예제1 에 대한 table 블럭들과 game_board 블럭틀의 집합은 다음과 같다.
•  

table 블럭	[[[1], [1]], [[1, 1, 0], [0, 1, 0], [0, 1, 1]], [[0, 1], [1, 1], [0, 1]], [[1, 1], [0, 1]], [[1, 1]]]
game_board 비어있는 틀	[[[1, 1, 0], [0, 1, 0], [0, 1, 1]], [[1], [1]], [[1, 1], [1, 0]], [[0, 1, 0], [1, 1, 1]], [[0, 1], [1, 1]], [[1]]]

 

 

 

Step 3

 answer = 0
    for i in blocks :
        for shape in empty_board :
            if len(i)*len(i[0]) == len(shape)*len(shape[0]) :
                # print("블럭 : {}, 비어있는 틀 : {}".format(i, shape))
                block = i
                find = False
                for _ in range(4) :
                    if block == shape :
                        # print("블럭 : {}, 비어있는 틀 : {} 이 같음".format(block, shape))
                        for c in block :
                            answer += c.count(1)
                        shape[0][0] = -1 # 이미 블럭을 끼웠으므로 -1 을 넣어 다른 블럭이 오지 못하게 함
                        find = True
                        break
                    else :
                        block = spin(block)
                #         print("회전한 블럭 : {}".format(block))
                # print("\n")
                if find : break
                
    
    return answer

• 이제 table 블럭과 game_board 의 틀의 모양을 비교해줄 일만 남았다.
• for문을 통해 비교하는데, 만약 블럭좌표의 행 x 열 을 한 값이 같지 않다면, 애초에 모양이 같지 않음을 뜻하므로 비교를 하지 않고 넘어간다.
• 만약, 블럭과 틀 모양이 같다면? 블럭 사각형에서 1의 개수만큼 answer 에 더해준다. 다음번에 이미 채워진 해당 틀모양이 비교대상이 되지 않도록 틀의 한 좌표값을 -1 로 채워, 절대 같은 모양이 될 수 없도록 한다.
• 그렇지않다면, 블럭을 회전하여 한번 더 비교해야 한다.

 

Step 4

def spin(board) :
    n = len(board) # 행 길이
    m = len(board[0]) # 열 길이
    result = [[0] * n for _ in range(m)] # 90도 회전한 결과는 행과 열이 반대됨
    for i in range(n):
        for j in range(m):
            result[j][n - 1 - i] = board[i][j]
    return result

• 행 x 열로 구성된 사각형을 90도 회전하는 방법은 위와 같다.
• 일단, 사각형의 행과 열이 바뀌므로 그에 맞는 result 이차원 배열을 생성해준다.
• 그런다음 result[j][n - 1 - i] = board[i][j] 라는 공식에 따라 회전을 진행한다.
• 이는 외워두는 것이 좋을 것!

 

 

요약

즉, 정리하자면 다음과 같다.

 

1. 블럭과 블럭이 들어갈 틀모양을 좌표로 추출해낸다.

아래의 game_board 에서 추출한 초록색 틀의 좌표들은 [1,0],[1,1],[1,2] 가 될 것이다.

 

2. 좌표가 [0,0] 에서 시작하도록 변경하고, 사각형으로 만들어 해당하지 않는 부분은 0으로 채운다.

(0,0) 값: 1	(0,1) 값: 1
(1,0) 값 :1	(1,1) 값: 0

 

3. block의 블럭들과 game_boards 의 틀 들을 비교하며, 같은 모양이라면 해당 사각형에서 1의 개수를 정답에 더한다.

 

4. 만약, 모양이 다르다면 90도씩 회전해가며 비교해본다.

 

 

출력으로 보는 과정

기댓값	14
실행 결과	테스트를 통과하였습니다.
출력	블럭 : [[1], [1]], 비어있는 틀 : [[1], [1]] 블럭 : [[1], [1]], 비어있는 틀 : [[1], [1]] 이 같음 채울 수 있는 칸 : 2 블럭 : [[1, 1, 0], [0, 1, 0], [0, 1, 1]], 비어있는 틀 : [[1, 1, 0], [0, 1, 0], [0, 1, 1]] 블럭 : [[1, 1, 0], [0, 1, 0], [0, 1, 1]], 비어있는 틀 : [[1, 1, 0], [0, 1, 0], [0, 1, 1]] 이 같음 채울 수 있는 칸 : 7 블럭 : [[0, 1], [1, 1], [0, 1]], 비어있는 틀 : [[0, 1, 0], [1, 1, 1]] 회전한 블럭 : [[0, 1, 0], [1, 1, 1]] 블럭 : [[0, 1, 0], [1, 1, 1]], 비어있는 틀 : [[0, 1, 0], [1, 1, 1]] 이 같음 채울 수 있는 칸 : 11 블럭 : [[1, 1], [0, 1]], 비어있는 틀 : [[1, 1], [1, 0]] 회전한 블럭 : [[0, 1], [1, 1]] 회전한 블럭 : [[1, 0], [1, 1]] 회전한 블럭 : [[1, 1], [1, 0]] 블럭 : [[1, 1], [1, 0]], 비어있는 틀 : [[1, 1], [1, 0]] 이 같음 채울 수 있는 칸 : 14 블럭 : [[1, 1]], 비어있는 틀 : [[-1], [1]] 회전한 블럭 : [[1], [1]] 회전한 블럭 : [[1, 1]] 회전한 블럭 : [[1], [1]] 회전한 블럭 : [[1, 1]]