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

문제

• 퍼즐 조각을 1x1 칸으로 나뉜 정사각형 게임 보드의 빈 공간에 적절히 올려놓으려 한다.
  • 3 <= 보드 크기 <= 50
  • 0은 빈칸, 1은 채워진 칸
• 조각을 올려놓을 때의 규칙 
  • 조각은 한 번에 하나씩 채워 넣는다.
  • 조각을 회전시킬 수 있다.
  • 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안된다.
• 최대한 많은 조각을 채워 넣을 경우 총 몇 칸을 채울 수 있는지 리턴하기

 

풀이 (초기 생각)

• 보드에서 빈 공간 추출 + 테이블에서 조각을 추출 (bfs)
  • 보드는 0을, 테이블에서는 1의 값을 추출해야 한다. flag 값을 정해둬서 해당 값을 가진 조각을 추출하도록 한다.
  • 각 블록의 (최소 행, 최소 열) 을 (0, 0)으로 설정한다. => 모든 인덱스에서 (최소 행, 최소 열) 값을 뺀다.
  • 행-열 오름차순으로 정렬한다.
  • 딕셔너리를 이용해 각 조각의 개수를 키로 각 조각을 저장한다.
• 각 퍼즐마다 빈칸을 채울 수 있는지 확인
  
  • 퍼즐 회전을 해야하므로 퍼즐 기준으로 확인한다. (count)
  • 각 퍼즐을 포함하는 정사각형을 회전시키고, 조각을 추출한다. (rotate + bfs)
  • 각 퍼즐과 빈칸의 인덱스가 정확히 일치하면 빈칸을 채울 수 있다. (check)

 

from collections import deque
from collections import defaultdict

dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)

# 조각 정보 리턴하기
def bfs(start, visited, n, flag):
    q = deque([start])
    visited[start[0]][start[1]] = 1-flag
    ret = []    # 조각의 각 인덱스 리스트
    
    while q:
        x, y = q.popleft()
        ret.append((x, y))

        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == flag:
                q.append((nx, ny))
                visited[nx][ny] = 1-flag
    
    # 조각의 가장 작은 행과 열의 값을 (0, 0)으로 설정한다.
    x, y = min([r[0] for r in ret]), min([r[1] for r in ret])
    return [ (r[0]-x, r[1]-y) for r in ret]

# 각 빈칸 별로 몇 칸을 채울 수 있는지 확인하기
def count(empties, puzzles, k):
    cnt = 0     # 채울 수 있는 빈칸의 수
    visited = [False] * len(empties)        # 빈칸을 채웠는지 확인 리스트
    for p in puzzles:
        puzzles_list = rotate_puzzle(p, k)  # 퍼즐 회전하기
        # 각 빈 칸별로 해당 퍼즐로 채울 수 있는지 확인하기
        for i, e in enumerate(empties):
            if not visited[i] and check(e, puzzles_list):
                cnt += k
                visited[i] = True
                break
    return cnt

# 퍼즐이 빈 칸과 일치하는지 확인하기
def check(empty, puzzles_list):
    for puzzle in puzzles_list:
        if not (set(empty) - set(puzzle)) :
            return True
    return False

# 퍼즐 회전시킨 리스트 반환
def rotate_puzzle(puzzle, k):
    n = 0               # 정사각형 크기
    for i in range(1, k+1):
        if k <= i*i :
            n = i
    
    cube = [[0]*n for _ in range(n)]
    for x, y in puzzle:
        cube[x][y] = 1

    ret = [cube, ]      # 각 cube 회전시킨 결과
    for _ in range(3):
        ret.append(rotate(ret[-1], n))
    
    puzzles_list = [puzzle, ]   # 각 cube에서 조각 추출하기
    for cube in ret[1:]:
        for i in range(n):
            for j in range(n):
                if cube[i][j] == 1 :
                    puzzles_list.append(bfs((i,j), cube, n, 1))
    return puzzles_list

# 90도 회전시키기
def rotate(cube, n):
    tmp = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            tmp[i][j] = cube[j][n-1-i]
    return tmp
            
def solution(game_board, table):
    n = len(game_board)
    
    # 빈 공간 리스트 empties{'칸 개수': []}
    empties = defaultdict(list)  
    visited = [ g[:] for g in game_board]
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0 :
                ret = bfs((i, j), visited, n, 0)
                empties[len(ret)].append(ret)
    
    # 조각 리스트 puzzles{'퍼즐 개수': []}
    puzzles = defaultdict(list)
    visited = [ t[:] for t in table]
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 1 :
                ret = bfs((i, j), visited, n, 1)
                puzzles[len(ret)].append(ret)
    
    # 각 빈칸 별로 채울 수 있는지 확인하기
    answer = 0
    for k in empties:
        if puzzles[k]:
            answer += count(empties[k], puzzles[k], k)
    return answer

 

 

 

References

• 프로그래머스 Lv3 퍼즐 조각 채우기