[프로그래머스] 위클리 챌린지_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에는 반드시 하나 이상의 블록이 놓여 있습니다.

💡 문제 푸는 방법

1. game_board에서 빈칸 찾아서 리스트에 넣어주기

2. table에서 블럭을 찾아서 리스트에 넣어주기

3. 두 리스트를 돌면서 서로 맞는 모양 찾으면 answer에 더해주기

(단, 방향을 4방향으로 회전할 수 있기 때문에 돌리면서 맞는 모양을 찾아주어야 한다!)

 

코딩초보인 나한테는 넘나 어려운 문제였다.

https://latte-is-horse.tistory.com/190

[프로그래머스 위클리 챌린지 (lv3)] 3주차_퍼즐 조각 채우기 (DFS)

이 분의 코드를 참고해서 열심히 공부했다.. Respect..!

def dfs(matrix, i, j, find):
    dx = [1, 0, -1, 0]
    dy = [0, -1, 0 ,1]
    stack = [[i,j]]
    result = [(i,j)]

    while stack:
        a, b = stack.pop()
        matrix[a][b] = -1
        for i in range(4):
            x, y = a + dx[i], b + dy[i]
            if x >= 0 and x < len(matrix) and y >= 0 and y < len(matrix) and matrix[x][y] == find:
                matrix[x][y] = -1
                stack.append([x,y])
                result.append((x,y))
    return result

def move(piece):
    min_x = min([x[1] for x in piece])
    min_y = min([x[0] for x in piece])
    piece = [(p[0]-min_y, p[1]-min_x) for p in piece]
    return sorted(piece)

def rotate(piece):
    if len(piece) == 1:
        return piece
    result = [piece]
    width = max(x[1] for x in piece) - min(x[1] for x in piece)
    height = max(x[0] for x in piece) - min(x[0] for x in piece)
    moves = [height, width, height]

    for i in range(3):
        lst = []
        
        for j in result[-1]:
            lst.append((j[1],j[0]))
            
        lst = [(x[0], moves[i] - x[1]) for x in lst]
        result.append(sorted(lst))

    return min(result)

def solution(game_board, table):
    answer = 0
    spaces, pieces = [], []
    for i in range(len(table[0])):
        for j in range(len(table)):
            if table[i][j] == 1:
                piece = dfs(table, i, j, 1)
                piece = move(piece)
                piece = rotate(piece)
                pieces.append(piece)

            if game_board[i][j] == 0:
                space = dfs(game_board, i, j, 0)
                space = move(space)
                space = rotate(space)
                spaces.append(space)

    for space in spaces:
            for piece in pieces:
                if space == piece:
                    answer += len(piece)
                    pieces.remove(piece)
                    break
                
    return answer