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

문제

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

프로그래머스

 

 

---

 

주요 아이디어

처음에는 좌 -> 우, 상 -> 하 방향으로 board 판을 이동하면서 계속 탐색해나가는 과정을 생각했으나 풀이 과정이 복잡해져서 중간에 포기했다.

핵심 아이디어는 빈칸의 좌표 & 블록의 좌표를 dfs로 구하고 해당 좌표를 (0, 0) 위치로 이동시키는 것이다.

이렇게 하면 비교하기도 편해지고, 

단, 주의할 점은 블록 회전이 가능하다는 것! -> 즉 회전 횟수 4번의 경우에 대해서 모두 체크해줘야 한다.

---

 

코드 구현 (Python 3)

 

 

import copy

def dfs(graph, x, y, position, n, cmd):
    direction = [[-1, 0], [0, 1], [1, 0], [0, -1]] # 방향
    
    result = [position]
    
    # 공백 찾을 때 / 블록 찾을 때에 따라 target_num 다르게
    if cmd == 'blank':
        target_num = 0
    else:
        target_num = 1
    
    # 인접 노드 방문
    for i in range(4):
        px = x + direction[i][0]
        py = y + direction[i][1]
        
        if 0 <= px < n and 0 <= py < n and graph[px][py] == target_num:
            graph[px][py] = -1 # 방문 처리
            result = result + dfs(graph, px, py, [position[0] + direction[i][0], position[1] + direction[i][1]], n, cmd)
    
    return result

def rotate(table):
    n = len(table)
    rotated = [[0] * n for _ in range(n)]
    
    # table 90도 뒤집기
    for i in range(n):
        for j in range(n):
            rotated[j][n-i-1] = table[i][j]
    
    return rotated


def solution(game_board, table):
    # 가로 길이 = 세로 길이
    n = len(game_board)
    answer = 0
    # game_board 내의 빈칸 좌표 구해서 리스트에 넣기
    blank = []
    
    for i in range(n):
        for j in range(n):
            if game_board[i][j] == 0:
                game_board[i][j] = -1
                # board, x, y, position, n, command
                blank.append(dfs(game_board, i, j, [0, 0], n, 'blank')[1:])
    
    # 4번 회전 하기
    for _ in range(4):
        table = rotate(table)
        copy_table = copy.deepcopy(table) # 변경 방지 (원래대로 되돌리기 용)
        
        for i in range(n):
            for j in range(n):
                if copy_table[i][j] == 1:
                    copy_table[i][j] = -1 # 방문처리
                    block = dfs(copy_table, i, j, [0, 0], n, 'block')[1:]
                    
                    # 만약 블록이 공백 안에 들어가면?
                    if block in blank:
                        # 공백 리스트에서 제거
                        blank.pop(blank.index(block))
                        # 채운 칸 수 더해주기
                        answer += (len(block) + 1)
                        
                        table = copy.deepcopy(copy_table)
                    else:
                        copy_table = copy.deepcopy(table)
    
    return answer

 

 

 

제출 결과

---

 

코드 개선 방안

시험 시간 내에 이런 로직을 생각해서 정확히 구현할 수 있을지 의문이다.. 유사한 유형 문제를 더 많이 풀어보자!