개발조아

[프로그래머스] 위클리 챌린지 3주차 퍼즐 조각 채우기 파이썬 본문

알고리즘/프로그래머스

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

개발조아 2021. 8. 23. 16:57
728x90

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/84021

 

코딩테스트 연습 - 3주차

[[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0

programmers.co.kr

질문하기에 너무 공감됐던 글이다.

1,2주차는 쉬웟는데 갑자기 너무 어려워졌던 문제였다.

 

올해 LG CNS 8월 입사자 4번 문제랑 같은 문제였던거 같다.

각각의 블럭들을 어떻게 관리를 해야할지 생각이 나지 않아 못풀었던 문제인데 최근에 비슷한 문제를 풀고나서 다시 풀었다.

구현해야할 것도 확인해야할 것도 많다 보니 소스가 너무 길어졌다. 개선해야겠지만 손이 안간다...

 

백준의 스티커 붙이기와 문제가 유사하다.

문제 링크 : https://www.acmicpc.net/problem/18808

 

18808번: 스티커 붙이기

혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연

www.acmicpc.net

 

풀이하려는 문제도 스티커 붙이기 처럼 입력으로 주어지는 모양을 적절히 회전 시켜서 칸에 채우는 문제이다.

그래서 그때 썼던 회전 방식을 이용했다.

 

풀이 순서는 다음과 같다.

 

 

1. 데이터 생성

1.1 game_board의 빈칸 재구성

우선 나는 game_board의 빈칸을 구역으로 나누고 해당 구역 포함할 수 있는 최소한의 크기의 사각형의 시작점을 구했다. 나는 블럭 별로 배열을 만들어 game_board와 비교하기 때문에 시작점을 알아야한다.

game_board                                           table         

 

game_board 빨간 박스와 table의 빨간 박스의 모든 값을 비교하기 때문에 시작점을 구해야 한다.

 

BFS로 빈칸을 2로 바꿔주면서 해당 빈칸을 다 아우룰수 있는 최소한의 사각형의 가장 작은 x,y 각각 저장했다.

 

그리고 해당 칸의 빈칸도 새주었는데 이는 해당 칸에 블럭을 넣을 때 개수가 같은 블럭만 체크하기 위함이다. 빈칸과 블록의 칸 개수가 같지 않으면 볼 필요가 없다.

 

def check_empty_block(game_board):
    for sx in range(len(game_board)):
        for sy in range(len(game_board)):
            if game_board[sx][sy] == 0:
                check_empty_block_bfs(sx, sy, game_board)

def check_empty_block_bfs(sx, sy, game_board):
    global empty_cell
    q = deque([(sx, sy)])
    game_board[sx][sy] = 2

    cnt = 0
    x1=y1=9876543210

    while q:
        x, y = q.pop()
        x1 = min(x1, x)
        y1 = min(y1, y)
        cnt += 1
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if point_validator(nx, ny, game_board, 0):
                game_board[nx][ny] = 2
                q.appendleft((nx, ny))

    empty_cell.append((x1, y1, cnt))

 

1.2 블록 추출하기

블록을 따로 저장한 것은 블록을 회전하기 위해서이다.

table 배열에서 각각의 블록을 따로 빼서 해당 블록을 아우룰수 있는 최소한의 크기의 배열로 다시 만들었다.

이과정은 BFS로 구현하였고, 블럭 배열의 빈칸은 1로 블럭이 있는 곳은 2로 표시하였다.

배열의 크기를 구하기 위해 가장 작은 x,y의 값과 가장 큰 x,y의 값들을 각각 저장하고

x값의 차이 + 1 이 행개수, y 값의 차이 + 1이 열의 개수이다.

각각의 블록들은 3가지로 구성돼있다.

0번째는 칸의 개수, 1번째는 블록의 모양, 2번째는 블록 사용 상태이다.

 

def set_block_board(table):
    for sx in range(len(table)):
        for sy in range(len(table)):
            if table[sx][sy] == 1:
                set_block_board_bfs(sx, sy, table)

def set_block_board_bfs(sx, sy, table):
    global blocks
    q = deque([(sx, sy)])
    table[sx][sy] = 2

    points = []
    x1 = y1 = 9876543210
    x2 = y2 = -1
    while q:

        x, y = q.pop()
        points.append((x, y))
        x1 = min(x1, x)
        y1 = min(y1, y)

        x2 = max(x2, x)
        y2 = max(y2, y)
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if point_validator(nx, ny, table, 1):
                table[nx][ny] = 2
                q.appendleft((nx, ny))

    r, c = x2 - x1 + 1, y2 - y1 + 1
    block = [[1] * c for _ in range(r)]
    for x, y in points:
        x -= x1
        y -= y1
        block[x][y] = 2

    blocks.append([len(points), block, False])

 

2. 블럭 넣기

2.1 사용가능한 블럭 체크

이는 재귀로 구현하였다. 현재 넣으려는 빈칸에 아직 사용하지 않은 블럭들을 모두 비교하였다.

1차적으로 블럭의 사용상태를 확인하고 다음에 빈칸과 블럭의 칸 개수가 맞는지 확인하고 블럭을 돌려가면서 넣을 수 있는지 확인하였다.

 

근데 만약 모든 블럭을 확인했는데 넣을 수 없다면 그 칸은 그냥 건너뛴다.

 

2.2 블럭 넣어보기

앞에서 empty_cell에 빈칸 사각형의 시작 인덱스를 저장해놨다. 이점부터 블럭 배열의 크기 만큼 모든 점들을 비교하여 모두 같다면 넣고 아니라면 블럭을 회전한다.

 

블럭 회전은 행을 열로 바꾸면 된다.

인덱스만 잘 조절하면 어렵지 않게 할 수 있다.

 

3. 답 찾기

재귀를 돌면서 마지막 빈칸까지 모두 확인 했다면 답을 구해야한다.

규칙에 맞게 최대한 많은 블럭을 넣을 때의 총 몇칸을 넣는지 구하는 것이다.

그래서 answer을 튜플로 두개 값을 저장해서 max로 가장 큰값을 구했다.

첫번째 값은 넣은 블럭의 개수고 두번째 값은 블럭이 차지하는 칸 수 이다.

max는 첫번째가 같으면 두번째를 기준으로 비교하기 때문에 같은 갯수의 블럭을 넣어도 구별이 된다.

 

def insert_block(game_board, total, total_cnt, cell_idx):
    global answer

    if cell_idx == len(empty_cell):
        answer = max(answer, (total_cnt,total))
        return

    sx, sy, cnt = empty_cell[cell_idx]
    flag = False
    for idx in range(len(blocks)):
        block_cnt, block, status = blocks[idx]
        if status:
            continue
        if block_cnt == cnt:
            if insert_block_check(game_board, block, sx, sy):
                blocks[idx][2] = True
                flag = True
                break
    if flag:
        insert_block(game_board, total+cnt, total_cnt+1, cell_idx + 1)
    else:
        insert_block(game_board, total, total_cnt, cell_idx + 1)

def insert_block_check(game_board, block, sx, sy):
    for _ in range(4):
        r, c = len(block), len(block[0])
        flag = True
        if sx+r <= len(game_board) and sy+c <= len(game_board):
            for x in range(sx, sx + r):
                for y in range(sy, sy + c):
                    if game_board[x][y] != block[x - sx][y - sy]:
                        flag = False
                        break
                if not flag:
                    break
            if flag:
                return True
        block = rotate_block(block)
    return False
    
def rotate_block(block):
    r, c = len(block), len(block[0])
    tmp = [[0]*r for _ in range(c)]

    for x in range(r):
        for y in range(c):
            tmp[y][r-x-1] = block[x][y]

    return tmp

 

 

전체 소스

from collections import deque

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

blocks = []
empty_cell = []


def solution(game_board, table):
    global answer
    answer = (0,0)

    check_empty_block(game_board)
    set_block_board(table)

    insert_block(game_board, 0, 0, 0)

    return answer[1]


def insert_block(game_board, total, total_cnt, cell_idx):
    global answer

    if cell_idx == len(empty_cell):
        answer = max(answer, (total_cnt,total))
        return

    sx, sy, cnt = empty_cell[cell_idx]
    flag = False
    for idx in range(len(blocks)):
        block_cnt, block, status = blocks[idx]
        if status:
            continue
        if block_cnt == cnt:
            if insert_block_check(game_board, block, sx, sy):
                blocks[idx][2] = True
                flag = True
                break
    if flag:
        insert_block(game_board, total+cnt, total_cnt+1, cell_idx + 1)
    else:
        insert_block(game_board, total, total_cnt, cell_idx + 1)

def insert_block_check(game_board, block, sx, sy):
    for _ in range(4):
        r, c = len(block), len(block[0])
        flag = True
        if sx+r <= len(game_board) and sy+c <= len(game_board):
            for x in range(sx, sx + r):
                for y in range(sy, sy + c):
                    if game_board[x][y] != block[x - sx][y - sy]:
                        flag = False
                        break
                if not flag:
                    break
            if flag:
                return True
        block = rotate_block(block)
    return False


def rotate_block(block):
    r, c = len(block), len(block[0])
    tmp = [[0]*r for _ in range(c)]

    for x in range(r):
        for y in range(c):
            tmp[y][r-x-1] = block[x][y]

    return tmp


def check_empty_block(game_board):
    for sx in range(len(game_board)):
        for sy in range(len(game_board)):
            if game_board[sx][sy] == 0:
                check_empty_block_bfs(sx, sy, game_board)

def check_empty_block_bfs(sx, sy, game_board):
    global empty_cell
    q = deque([(sx, sy)])
    game_board[sx][sy] = 2

    cnt = 0
    x1=y1=9876543210

    while q:
        x, y = q.pop()
        x1 = min(x1, x)
        y1 = min(y1, y)
        cnt += 1
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if point_validator(nx, ny, game_board, 0):
                game_board[nx][ny] = 2
                q.appendleft((nx, ny))

    empty_cell.append((x1, y1, cnt))

def set_block_board(table):
    for sx in range(len(table)):
        for sy in range(len(table)):
            if table[sx][sy] == 1:
                set_block_board_bfs(sx, sy, table)

def set_block_board_bfs(sx, sy, table):
    global blocks
    q = deque([(sx, sy)])
    table[sx][sy] = 2

    points = []
    x1 = y1 = 9876543210
    x2 = y2 = -1
    while q:

        x, y = q.pop()
        points.append((x, y))
        x1 = min(x1, x)
        y1 = min(y1, y)

        x2 = max(x2, x)
        y2 = max(y2, y)
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if point_validator(nx, ny, table, 1):
                table[nx][ny] = 2
                q.appendleft((nx, ny))

    r, c = x2 - x1 + 1, y2 - y1 + 1
    block = [[1] * c for _ in range(r)]
    for x, y in points:
        x -= x1
        y -= y1
        block[x][y] = 2

    blocks.append([len(points), block, False])


def point_validator(x, y, board, target):
    if x < 0 or y < 0 or x >= len(board) or y >= len(board):
        return False
    elif board[x][y] != target:
        return False
    return True

 

'알고리즘 > 프로그래머스' 카테고리의 다른 글

[프로그래머스] 광고 삽입 파이썬  (0) 2021.08.26
[프로그래머스] 합승 택시 요금 파이썬  (0) 2021.08.24
[프로그래머스] 순위 검색 파이썬  (0) 2021.08.13
[프로그래머스] 메뉴 리뉴얼 파이썬  (0) 2021.08.13
[프로그래머스] 정수 삼각형 파이썬  (0) 2021.08.13
'알고리즘/프로그래머스' Related Articles more
Comments