[백준 18808번] 스티커 붙이기

18808번: 스티커 붙이기

n, m, k = map(int,input().split())

paper = [[0]*m for _ in range(n)]

count = 0

for _ in range(k):
    r,c = map(int,input().split())

    sticker = [list(map(int,input().split())) for _ in range(r)]

    def check_available(paper,x,y,sticker,sticker_row_len,sticker_col_len): # 스티커를 붙일 수 있는지 확인하는 함수
        for i in range(sticker_row_len):
            for j in range(sticker_col_len):
                if sticker[i][j] == 1 and paper[x+i][y+j] == 1:
                    return False
        return True
    
    def add_area(paper,x,y,sticker,sticker_row_len,sticker_col_len): # 스티커를 붙이는 함수
        temp_paper = [item[:] for item in paper]
        for i in range(sticker_row_len):
            for j in range(sticker_col_len):
                if sticker[i][j] == 1:
                    temp_paper[x+i][y+j] = 1
        return temp_paper
    
    def rotate(sticker): # 2차원 배열을 90도 회전시키는 함수
        row_len = len(sticker)
        col_len = len(sticker[0])

        new_sticker = [[0]*row_len for _ in range(col_len)]

        for i in range(row_len):
            for j in range(col_len):
                new_sticker[j][row_len-1-i] = sticker[i][j]
        
        return new_sticker
        
    
    def paint(sticker): # 종이에 스티커를 붙이기 위해 모든 경우의 수를 시도하는 함수(성공하면 true 반환)
        global paper
        for i in range(n):
            for j in range(m):
                sticker_row_len = len(sticker)
                sticker_col_len = len(sticker[0])

                if 0 <= (i + sticker_row_len -1) < n and 0 <= (j + sticker_col_len -1) <  m:
                    if check_available(paper,i,j,sticker,sticker_row_len,sticker_col_len):
                        paper = add_area(paper,i,j,sticker,sticker_row_len,sticker_col_len)
                        return True
        return False

    if paint(sticker): # 종이에 바로 스티커를 붙이는데 성공하면 바로 다음 스티커로 continue
        continue

    for _ in range(3): # 90도 회전하면서 스티커를 붙일 수 있는지 확인, 붙이는데 성공하면 break
        sticker = rotate(sticker)
        if paint(sticker):
            break

for i in range(n):
    for j in range(m):
        if paper[i][j] == 1:
            count += 1

print(count)

 

이번 문제는 다소 문제가 길지만 전형적인 완전탐색 문제이다.

1. 각 스티커마다 종이(2차원 배열)에 붙일 수 있는 영역을 탐색
2. 해당 스티커를 바로 붙일 수 없다면 90도씩 회전해가며 탐색(0도, 90도, 180도, 270도)

각 스티커마다 2차원 배열을 순회해가며 붙일 수 있는 영역을 찾아야하는 것은 금방 파악할 수 있었는데, 스티커를 붙일 수 있는 여부를 확인하는 함수와 스티커를 붙이는 함수를 만드느라 시간이 조금 걸렸던 것 같다.(얕은 복사로 인한 문제를 방지하기 위해 깊은 복사)

    def rotate(sticker): # 2차원 배열을 90도 회전시키는 함수
        row_len = len(sticker)
        col_len = len(sticker[0])

        new_sticker = [[0]*row_len for _ in range(col_len)]

        for i in range(row_len):
            for j in range(col_len):
                new_sticker[j][row_len-1-i] = sticker[i][j]
        
        return new_sticker

 

그리고 무엇보다 가장 시간이 많이 잡아먹혔던 것은 바로 '2차원 배열을 90도 회전하는 함수'였다.

 

[Python] 2차원 배열 회전 알고리즘

직접 구현해보려고 하다가 시간이 너무 오래걸려서 위 블로그를 참고해서 행과 열의 크기와 상관없이 90도 회전시켜서 반환하는 함수를 직접 구현하게 되었다.

 

https://shoark7.github.io/programming/algorithm/rotate-2d-array

 

먼저 회전하고자 하는 2차원 배열의 행의 길이와 열의 길이를 구하고, 각 길이를 반대로 한 2차원 배열을 선언해준다. 그 후 새 배열[j][기존 배열의 행 개수 - 1 - i] = 기존 배열[i][j] 라는 점화식으로 값을 저장해주면 된다.

 

90도 회전하는 함수는 자주 사용할 수 있으므로 이번 기회에 암기하고 있어야겠다고 생각이 든 문제였다. 완전탐색에 대해 복습해볼 수 있었던 좋은 문제였다 :)