프로그래머스(programmers) 퍼즐 조각 채우기 python 정답 [DFS 풀이]

프로그래머스(programmers) 퍼즐 조각 채우기 python 정답 [DFS 풀이]

문제 링크

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

프로그래머스

문제 정답

입출력 예

입출력 예 시각화

import copy


d = [(-1,0),(0,1),(1,0),(0,-1)]
# 채울 칸과 놓을 조각을 찾는 함수
def dfs(graph, x, y, position, n, num):
    ret = [position]    
    for i in range(4):
        dx,dy = d[i]
        nx,ny = x + dx, y + dy                
        if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == num:
            graph[nx][ny] = 2
            ret = ret + dfs(graph, nx, ny, [position[0]+dx, position[1]+dy], n, num)    
    return ret

# 조각을 돌리기 위한 함수
def rotate(lst):
    n = len(lst)
    ret = [[0]*n for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            ret[j][n-1-i] = lst[i][j]
    
    return ret

def solution(game_board, table):
    answer = 0
    game_board_copy = copy.deepcopy(game_board)    
    n = len(game_board)
    board_slots = []
    # 빈공간을 모아둠
    for i in range(n):
        for j in range(n):
            if game_board_copy[i][j] == 0:
                game_board_copy[i][j] = 2
                result = dfs(game_board_copy, i, j, [0, 0], n, 0)[1:]
                board_slots.append(result)
    # 조각을 돌림
    for r in range(4):
        table = rotate(table)
        table_rotate_copy = copy.deepcopy(table)

        for i in range(n):
            for j in range(n):
                if table_rotate_copy[i][j] == 1:
                    table_rotate_copy[i][j] = 2
                    # 딱 맞는 조각만 채울 수 있음
                    result = dfs(table_rotate_copy, i, j, [0, 0], n, 1)[1:]
                    if result in board_slots:
                        board_slots.pop(board_slots.index(result))
                        answer += (len(result) + 1)
                        
                        table = copy.deepcopy(table_rotate_copy)
                        
                    else:
                        table_rotate_copy = copy.deepcopy(table)
    return answer

문제 해설

일단 가장 중요한 문제 조건을 파악해야 한다.

• 한 조각을 끼워넣었을 때, 주변에 빈 칸이 없어야 한다
• 해당 빈 칸을 두 조각으로 채우거나 하는것도 안된다
• 그렇다면 해당 빈칸에 딱 맞는 블록은 해당 모양밖에 없다
  • 같은 모양의 블록의 넣는 순서는 고려하지 않아도 된다.

따라서 대략적인 알고리즘은 이렇게 될 것이다.

1. 조각들을 모은다
2. 조각들 전체를 90도 회전해서 판에 최대한 끼워넣어본다
   • 4번 시도하면 된다.

그럼 구체적인 구현을 보자

 

일단 position 기준 offset을 이용해 빈 칸을 찾는 함수를 만든다.

이전 이미지에서 게임 보드에서는 0인 점, table에서는 1인 점을 찾는 것을 보았다.

모아야 하는 점은 각각 0과 1

num을 변수로, position을 기준 점으로 이용해 해당 점들의 좌표를 모은다

result = dfs(game_board_copy, i, j, [0, 0], n, 0)[1:] # 게임판 위 조각을 둘 수 있는 곳
result = dfs(table_rotate_copy, i, j, [0, 0], n, 1)[1:] # 조각들의 위치

result[1:] 이런식으로 슬라이스 하는 이유는 원점은 양쪽이 전부 포함하기에 비교할 필요가 없어서다.

해당 점들을 모으는 dfs 함수는 다음과 같다.

• graph와 num은 우리가 조건에 따라 입력해주며 (board는 0,table은 1)
• 다른 변수는 나머지는 재귀를 위해 사용한다.
• 그래프의 방문 여부를 2로 표시한다.

d = [(-1,0),(0,1),(1,0),(0,-1)]
# 채울 칸과 놓을 조각을 찾는 함수
def dfs(graph, x, y, position, n, num):
    ret = [position]    
    for i in range(4):
        dx,dy = d[i]
        nx,ny = x + dx, y + dy                
        if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == num:
            graph[nx][ny] = 2
            ret = ret + dfs(graph, nx, ny, [position[0]+dx, position[1]+dy], n, num)    
    return ret

그리고 90도 돌리는 함수를 다음과 같이 선언한다.

# 조각을 돌리기 위한 함수
def rotate(lst):
    n = len(lst)
    ret = [[0]*n for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            ret[j][n-1-i] = lst[i][j]
    
    return ret

이제 핵심 로직의 구현을 보자

먼저 board_slots에 방문 가능한 좌표들을 모아둔다.

이부분은 그렇게 복잡하지 않다.

board는 돌릴 필요가 없으며,

모든 게임 보드의 빈 칸좌표를 [0,0]을 기준점으로 모으면 맨 위쪽 꼭대기 좌표를 [0,0]으로 하도록 모든 빈 칸 좌표를 모을 수 있다.

import copy

def solution(game_board, table):
    answer = 0  
    n = len(game_board)
    board_slots = []
    # 빈공간을 모아둠
    for i in range(n):
        for j in range(n):
            if game_board[i][j] == 0:
            	# 방문 여부 체크
                game_board[i][j] = 2
                result = dfs(game_board, i, j, [0, 0], n, 0)[1:]
                board_slots.append(result)

이제 조각을 돌리는 부분을 처라해야 하는데,

분명 좀 더 효과적인 알고리즘은 있겠으나,

가장 간단한 방법은 조각이 놓여져 있는 table 자체를 돌리는 것이다.

그리고 다시 한 번 모든 조각 좌표를 [0,0]을 기준점으로 모으면 맨 위쪽 꼭대기 좌표를 [0,0]으로 하도록 모든 조각 좌표를 모을 수 있다.

 

정리하자면

• 모든 게임 보드의 빈 칸좌표를 [0,0]을 기준점으로 모으면 맨 위쪽 꼭대기 좌표를 [0,0]으로 하도록 모든 빈 칸 좌표를 모을 수 있다.
• 그리고 다시 한 번 모든 조각 좌표를 [0,0]을 기준점으로 모으면 맨 위쪽 꼭대기 좌표를 [0,0]으로 하도록 모든 조각 좌표를 모을 수 있다.
  • 왜 맨 위쪽 꼭대기가 0,0이 되는가?는 i,j가 가장 먼저 만나기 때문이다 

따라서 조각을 처리하는 부분은 돌리는 for문이 들어가며,

table_rotate_copy를 사용하여 회전 결과를 테스트한다

copy를 하는 이유는 아래와 같다.

• 방문 결과를 위해 해당 그래프를 조작하기에, table은 조작되지 않은 상태로 유지하기 위해

따라서, 모든 좌표에 대해  table_rotate_copy에 테스트 해보고,

조각을 사용 가능하면, 사용 여부를 table_rotate_copy를 이용해 table에 반영한다.

 

if 안에서 copy.deepcopy를 계속 사용해주는 이유는 이중 포문 루프 간 서로의 참조 효과를 끊기 위해서이다.

(안그러면 다음 루프때 방문처리 테스트가 table에 영향을 줄 수 있다)

table과 table_rotate_copy는 서로 직접적인 참조 관계가 없으며,

서로를 업데이트 하는 것은 계속 새로운 객체를 만들어 할당하면 사이드 이펙트를 피할 수 있다.

    # 조각을 돌림
    for r in range(4):
    	# 방문 기록 뮤테이션을 피하기 위해 카피함
        table = rotate(table)
        table_rotate_copy = copy.deepcopy(table)

        for i in range(n):
            for j in range(n):
                if table_rotate_copy[i][j] == 1:
                	# copy에 직접 방문 기록
                    table_rotate_copy[i][j] = 2
                    # 딱 맞는 조각만 채울 수 있음
                    result = dfs(table_rotate_copy, i, j, [0, 0], n, 1)[1:]
                    # 해당 조각을 끼워 넣을 수 있으면, table에 방문 기록 반영
                    if result in board_slots:
                        board_slots.pop(board_slots.index(result))
                        answer += (len(result) + 1)                        
                        table = copy.deepcopy(table_rotate_copy)
                        
                    # 끼워넣을 수 없으면, 테이블에 방문 기록 미반영
                    # table_rotate_copy는 모든 i,j에 대해 사용하므로 매반 초기화 해줘야 함
                    else:
                        table_rotate_copy = copy.deepcopy(table)