[프로그래머스/python] 위클리 챌린지 3주차 : 퍼즐 조각 채우기

문제 설명

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

 

정답

# dfs 이용하여 이차원 리스트의 블록 모양 리스트 저장 함수
def dfs(i, j, board, visited, empty, n):
    section = []
    stack = [(i, j)]
    while stack:
        x, y = stack.pop()
        if x >= 0 and y >= 0:   # 인덱스 체크
            try:
                if visited[x][y] == False and board[x][y] == n:
                    visited[x][y] = True
                    section.append((x,y))
                    
                    stack.append((x-1, y))
                    stack.append((x+1, y))
                    stack.append((x, y-1))
                    stack.append((x, y+1))
                    
            except IndexError:
                continue
    empty.append(sorted(section))

# 블록의 위치를 (0,0)을 기준으로 변경하는 함수
def standard_0(b):
    tmp = []
    std_x = b[0][0]
    std_y = b[0][1]
    for x, y in b:
        tmp.append((x-std_x, y-std_y))
    return sorted(tmp)


def solution(game_board, table):
    answer = []
    N = len(game_board)

    visited_board = [list(False for _ in range(N)) for _ in range(N)]
    empty_board = []    # game_board의 빈자리 좌표 리스트 
    
    visited_table = [list(False for _ in range(N)) for _ in range(N)]
    empty_table = []    # table의 블록 좌표 리스트

    # dfs 이용하여 game_board의 빈 자리 좌표 리스트 empty_board에 저장
    for i in range(N):
        for j in range(N):
            if visited_board[i][j] == False and game_board[i][j] == 0:
                dfs(i, j, game_board, visited_board, empty_board, 0)

    # dfs 이용하여 table의 블록 좌표 리스트 empty_table에 저장
    for i in range(N):
        for j in range(N):
            if visited_table[i][j] == False and table[i][j] == 1:
                dfs(i, j, table, visited_table, empty_table, 1)
    
    # standard 함수 이용하여 empty_table의 블록 좌표를 (0,0) 기준으로 변경 후 blocks에 저장
    blocks = []
    for block in empty_table:
        blocks.append(standard_0(block))


    # 이차원 리스트 한칸씩 돌아보며 맞는 자리 있는지 확인 함수
    def match(block):  
        for x in range(N):
            for y in range(N):
                move = []
                for _x, _y in block:
                    new_x = x+_x
                    new_y = y+_y
                    if new_x >= 0 and new_y >=0:    # 인덱스 체크
                        try:
                            _ = game_board[x+_x][y+_y]  # 인덱스 체크
                            move.append((x+_x, y+_y))
                        except IndexError:
                            break
                    else:
                        break
                if len(block) == len(move) and move in empty_board: # 맞는 자리 찾음
                    empty_board.remove(move)    # 빈자리 삭제
                    answer.extend(move)
                    return True
        return False

    # 블록 90도 회전 함수
    def rotate_90(block):
        new = []
        for x, y in block:
            new.append((y, N-1 - x))
        return standard_0(new)
        

    # 블록 하나씩 맞는 자리 있는지 살펴보고 없으면 회전 후 찾기 반복
    for block in blocks:
        for _ in range(4):
            if match(block) == False:       # 맞는 자리 없음
                block = rotate_90(block)    # 블록 회전
            else:   # 맞는 자리 찾음
                break

    return len(answer)

---

✔ 우선 game_board의 빈칸과 table에 있는 블록의 좌표값을 블록 단위로 각각 리스트에 저장하고

table에 있는 블록 리스트를 game_board의 모든 칸에 대입해보며 game_board의 빈칸과 일치하는지 확인한다.

일치하지 않는다면 회전 후 다시 대입하며 확인해본다.

 

💥 튜플의 값은 변경이 불가능하다

💥 블록의 좌표를 (0,0) 기준으로 옮겨야 board의 모든 칸 탐색이 가능하다.

💥 리스트의 인덱스가 음수인 경우는 IndexError에 걸리지 않으므로 따로 확인해주어야 한다.

 

1. dfs 함수

dfs를 이용하여 이차원 리스트 board에 있는 블록 모양의 좌표 리스트를 empty 리스트에 저장한다.

game_board에서는 값이 0인 블록을, table에서는 값이 1인 블록을 확인해주어야 하므로

인자 n을 통해 구별해준다.

stack.pop() 좌표를 기준으로 상하좌우의 좌표를 stack에 넣어준다.

이때 stack.pop()의 값이 board 인덱스 안에 있는지 확인 후 진행해야 한다.

인덱스가 음수인 값일 때는 if문을 통해 확인하고, 인덱스가 오른쪽으로 벗어났을 때는 except를 통해 확인한다.

def dfs(i, j, board, visited, empty, n):
    section = []
    stack = [(i, j)]
    while stack:
        x, y = stack.pop()
        if x >= 0 and y >= 0:   # 인덱스 체크
            try:
                if visited[x][y] == False and board[x][y] == n:
                    visited[x][y] = True
                    section.append((x,y))
                    
                    stack.append((x-1, y))
                    stack.append((x+1, y))
                    stack.append((x, y-1))
                    stack.append((x, y+1))
                    
            except IndexError:
                continue
    empty.append(sorted(section))

 

2. standard_0 함수

dfs 함수를 통해 table에서 얻은 블록 좌표 리스트 empty_table을

(0,0)에서부터 맞춰보며 빈칸 리스트인 empty_board와 비교해볼 것이다.

(0,0)에서 순차적으로 모든 칸을 살펴보기 위해서는

empty_table의 블록이 (0,0)을 기준으로 위치해있어야한다.

블록 b의 첫번째 좌표 값을 (0,0)에 맞추고 나머지 좌표도 이에 따라 옮겨준다.

💥 이때 좌표를 나타내는 튜플 값은 변경이 불가능하므로 변경이 아닌 다시 만들어 return 한다.

def standard_0(b):
    tmp = []
    std_x = b[0][0]
    std_y = b[0][1]
    for x, y in b:
        tmp.append((x-std_x, y-std_y))
    return sorted(tmp)

 

3. match 함수

모든 칸을 돌면서 empty_board에 저장된 빈자리와 같은 모양인지 확인한다.

모든 칸을 돌 때 우선 인덱스 범위가 맞는지 확인한다.

if 문을 통해 인덱스가 음수로 넘어가는지 확인하고 

_ 변수를 이용하여 인덱스 범위가 넘어갈 경우 except에 걸리도록 한다.

💥 except 때문에 block의 일부만 move에 저장되는 경우가 있으므로 

block의 길이와 move의 길이가 같은지 확인하여 block의 전부가 move에 저장되었는지 확인 후

empty_board에 맞는 자리가 있는지 확인한다.

맞는 자리가 있다면 더이상 비어있는 자리가 아니기 때문에 empty_board에서 삭제하고 answer에 좌표를 저장한다.

def match(block):  
        for x in range(N):
            for y in range(N):
                move = []
                for _x, _y in block:
                    new_x = x+_x
                    new_y = y+_y
                    if new_x >= 0 and new_y >=0:    # 인덱스 체크
                        try:
                            _ = game_board[x+_x][y+_y]  # 인덱스 체크
                            move.append((x+_x, y+_y))
                        except IndexError:
                            break
                    else:
                        break
                if len(block) == len(move) and move in empty_board: # 맞는 자리 찾음
                    empty_board.remove(move)    # 빈자리 삭제
                    answer.extend(move)
                    return True
        return False

 

4. rotate_90 함수

기존 블록이 맞는 자리가 없을 경우 회전하여 다시 맞는 자리가 없는지 찾아야한다.

좌표를 90도 회전하면 x 값은 y, y 값은 N-1-x가 된다.

💥 이때도 마찬가지로 튜플 값은 변경 불가능하기 때문에 다시 만들어 return 해주어야한다.

def rotate_90(block):
        new = []
        for x, y in block:
            new.append((y, N-1 - x))
        return standard_0(new)