[Python] 프로그래머스(Lv3) - 3주차_ 퍼즐 조각 채우기

안녕하세요 :)

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

풀이

문제가 복잡하기 때문에 분할정복으로 나눠서 생각해봅시다 !
이 문제를 간단히 정의해보자면, 퍼즐을 찾고 table의 빈 공간에 적절히 올려 놓는 것입니다.
이를 위해 해야하는 행동은 크게 두가지 입니다.

1. 퍼즐을 찾는 것
2. 퍼즐을 테이블에 매치 시키는 것

1번 행위를 하기 위해서는 세부적인 함수들이 다음과 같이 필요합니다.
1) 퍼즐을 찾는 것은 bfs로 구현할 수 있습니다. 값이 1인 연결된 묶음을 찾으면 됩니다.
2) 찾은 다음 그 형태를 저장을 할 함수를 만들어 줍니다. (trans_puzzle)
저는 직사각형 형태로 형태를 만들었고 직사각형의 빈 곳은 0으로 채워주었습니다.

예를 들어 위와 같은 형태의 조각이라면
[[0, 1],
[1, 1],
[0, 1]]
로 만들어 줍니다.

2번 행위를 하기 위해서는 또 세부적인 함수들이 필요합니다.
1) 테이블의 빈 곳에 퍼즐을 넣어보고 인접한 칸이 비어있는지 확인하는 함수 (empty_side)
2) 인접한 칸이 비어있지 않다면 테이블에 조각을 넣고, 아니라면 원 상태로 되돌리는 함수 (is_match)
3) 조각을 회전시키는 함수(rotation)

이 2번 행위를 조각마다 반복하면서 테이블에 넣어보는데,
넣는데 성공했으면 is_match 함수가 true를 리턴합니다.
그럼 정답에 추가하면 되겠습니다!

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]


def rotation(puzzle):
    n = len(puzzle)
    m = len(puzzle[0])
    result = [[0] * n for _ in range(m)]
    for r in range(n):
        for c in range(m):
            result[c][n-1-r] = puzzle[r][c]

    return result


def bfs(i, j, table, check):
    puzzle = []
    n = len(table)
    q = [(i, j)]
    check[i][j] = True
    while q:
        x, y = q.pop()
        puzzle.append([x, y])
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if not (0 <= nx < n and 0 <= ny < n):
                continue
            if not check[nx][ny] and table[nx][ny] == 1:
                q.append((nx, ny))
                check[nx][ny] = True

    return puzzle


def trans_puzzle(puzzle_location):
    r_min, r_max = 100, -1
    c_min, c_max = 100, -1
    for location in puzzle_location:
        r, c = location
        r_min = min(r_min, r)
        r_max = max(r_max, r)
        c_min = min(c_min, c)
        c_max = max(c_max, c)

    r_len = r_max - r_min + 1
    c_len = c_max - c_min + 1
    trans = [[0] * c_len for _ in range(r_len)]
    for location in puzzle_location:
        x = location[0] - r_min
        y = location[1] - c_min
        trans[x][y] = 1

    return trans


def empty_side(game_board, puzzle, i, j):
    n = len(game_board)
    for x in range(len(puzzle)):
        for y in range(len(puzzle[0])):
            if puzzle[x][y] == 1:
                for k in range(4):
                    nx, ny = x + i + dx[k], y + j + dy[k]
                    if not (0 <= nx < n and 0 <= ny < n):
                        continue
                    if game_board[nx][ny] != 1:
                        return True

    return False


def is_match(puzzle, game_board):
    n = len(game_board)
    r = len(puzzle)
    c = len(puzzle[0])
    for i in range(n-r+1):
        for j in range(n-c+1):
            match = True
            for x in range(len(puzzle)):
                for y in range(len(puzzle[0])):
                    game_board[x+i][y+j] += puzzle[x][y]
                    if game_board[x+i][y+j] != 1:
                        match = False

            if empty_side(game_board, puzzle, i, j):
                match = False

            if match:
                return True
            else:
                for x in range(len(puzzle)):
                    for y in range(len(puzzle[0])):
                        game_board[x+i][y+j] -= puzzle[x][y]

    return False


def solution(game_board, table):
    n = len(game_board)
    answer = 0
    puzzles = []
    check = [[False] * n for _ in range(n)]
    puzzle_sum = []
    for i in range(n):
        for j in range(n):
            if table[i][j] == 1 and not check[i][j]:
                puzzle_location = bfs(i, j, table, check)
                puzzle = trans_puzzle(puzzle_location)
                puzzles.append(puzzle)
                puzzle_sum.append(len(puzzle_location))

    for idx, puzzle in enumerate(puzzles):
        for _ in range(4):
            puzzle = rotation(puzzle)
            if is_match(puzzle, game_board):
                answer += puzzle_sum[idx]
                break

    return answer