[프로그래머스] 퍼즐 조각 채우기 (Python)

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

프로그래머스

Status : Solved

Time : 00:43:12

 

---

 

 

문제 설명

 

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

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

* 문제 설명에 대한 예시는 위 링크를 참조해주세요

현재 게임 보드의 상태 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

 

 

---

 

 

풀이

기본적인 탐색 문제를 크게 확장한 문제. 구현을 어떻게 해야 할까 고민이 됬었다.

우선 table을 탐색하며 퍼즐 조각을 이루는 좌표를 저장한다. game_board에 이를 맞추어보기 위해서는 상대적인 좌표값을 저장하는 게 편하다. 또한, 퍼즐 조각은 뒤집을 수 없고 회전이 가능하므로 회전한 상태를 포함, 총 4가지 경우를 저장해야 한다. 좌표가 (x, y)라고 할 때 90도 회전 시 (-y, x)를 만족하고, 이를 3번에 거쳐 모든 경우의 수를 저장할 수 있다. 나 같은 경우는 이러한 퍼즐 조각 리스트에 "퍼즐의 총 크기"를 앞에 메타데이터로 저장하였다. 모든 퍼즐 좌표는 (0, 0)부터 차례대로 저장되었다.

 

다음은 game_board를 탐색할 차례인데, 말로 풀어 설명하자면 "game_board의 각 빈 칸에 모든 퍼줄 조각을 한 번씩 끼워 봄으로써 맞는 구멍인지 살펴보기" 가 목표가 된다. 우선 game_board에서 빈 칸을 발견한다면 그 빈 칸의 모든 좌표를 구하여, 각 좌표에 대해 퍼즐 좌표 리스트를 대입해 본다. 만약 1. 이미 사용한 퍼즐이거나 2. 들어갈 수 없는 구멍이거나(game_board[y][x]가 1 값을 포함하거나 유효하지 않음), 3. 인접한 빈 칸이 남아 있으면 안되므로(구멍의 총 크기와 앞서 저장한 퍼즐의 총 크기가 일치하지 않음) 이 경우를 제외한다. 남은 경우에 한해 퍼즐의 크기를 합산하면 정답을 얻을 수 있다.

 

풀이 코드

from collections import defaultdict, deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def search(x, y, map_list, visited, mode = 1) :
    result = [(0,0)]
    visited[y][x] = True
    n = len(map_list)
    q = deque([(0, 0)])
    while q :
        mx, my = q.popleft()
        for k in range(4) :
            ax, ay = x + mx + dx[k], y + my + dy[k]
            if -1 < ax < n and -1 < ay < n and map_list[ay][ax] == mode and not visited[ay][ax] :
                visited[ay][ax] = True
                q.append((mx + dx[k], my + dy[k]))
                result.append((mx + dx[k], my + dy[k]))
    
    return result

def rotate_list(lst) :
    result = [lst.copy()]
    
    for k in range(3) :
        tmp = list()
        for x, y in result[-1] :
            tmp.append((-y, x))
        result.append(tmp)
        
    return result

    
def make_piece_list(map_list) :
    n = len(map_list)
    visited = [[False]*n for _ in range(n)]
    result = list()
    
    for i in range(n) :
        for j in range(n) :
            if map_list[i][j] and not visited[i][j] :
                tmp = search(j, i, map_list, visited)
                tmp_size = len(tmp)
                result.append([tmp_size] + rotate_list(tmp))
                
    return result

def is_inside(map_list, piece, x, y) :
    n = len(map_list)
    for px, py in piece :
        ax, ay = x + px, y + py
        if ax < 0 or ay < 0 or ax >= n or ay >= n or map_list[ay][ax] :
            return False
    return True

def dfs(piece_list, map_list) :    
    n = len(map_list)
    m = len(piece_list)
    
    piece_visited = [False]*m
    visited = [[False]*n for _ in range(n)]
    result = 0
    for i in range(n) :
        for j in range(n) :
            if visited[i][j] or map_list[i][j] :
                continue
            empty_list = search(j, i, map_list, visited, 0)
            empty_size = len(empty_list)
            
            for ex, ey in empty_list :
                flg = False
                x, y = j + ex, i + ey
                
                for k in range(m) :
                    if piece_visited[k] :
                        continue
                    piece_size = piece_list[k][0]
                    if piece_size != empty_size :
                        continue

                    for _piece in piece_list[k][1:] :
                        if is_inside(map_list, _piece, x, y) :
                            result += piece_size
                            piece_visited[k] = True
                            flg = True
                            break
                    if flg :
                        break
                if flg :
                    break

    return result

def solution(game_board, table):
    piece_list = make_piece_list(table)
    answer = dfs(piece_list, game_board)
    
    return answer

풀이 완료!