[백준] 11808 스티커 붙이기 (파이썬 python)

 

 

문제 링크

 

https://www.acmicpc.net/problem/18808

18808번: 스티커 붙이기

 

 

 

문제 풀이

 

문제를 따라가며 조건에 맞게 구현해나가면 어렵지 않게 풀 수 있습니다.

다소 비효율적으로 푼 것 같기도 하지만 주어진 숫자 범위가 매우 작아 시간적인 문제는 없었습니다.

 

저는 세 개의 함수로 나누어 풀이했습니다.

 

1) 모눈종이를 붙일 수 있는지 여부를 확인하는 함수

 

def check(r, c, sticker, start_x, start_y):
    for x in range(r):
        for y in range(c):
            if sticker[x][y] and graph[start_x + x][start_y + y]:
                return False
    return True

 

스티커가 붙어있는 칸과 노트북의 칸을 비교하여 붙일 수 있는지 여부를 파악합니다.

만약, 노트북 위 스티커를 붙여야 하는 위치에 이미 스티커가 붙어있다면 False를 반환합니다.

start_x와 start_y는 모눈종이를 붙이기 시작할 위치입니다.

노트북이 모눈종이 크기보다 같거나 크기 때문에 시작점이 다양하게 나타날 수 있습니다.

 

 

2) 모눈종이를 붙이는 함수

 

def attach(r, c, sticker, start_x, start_y):
    for i in range(r):
        for j in range(c):
            if sticker[i][j]:
                graph[i + start_x][j + start_y] = 1

 

마찬가지로 시작점을 고려해서 스티커가 존재하는 칸을 1로 바꿔줍니다.

 

 

3) 각 스티커에 대한 행위를 관리하는 함수

 

def check_and_attach():
    r, c = map(int, input().split())
    sticker = [list(map(int, input().split())) for _ in range(r)]
    for dir in range(4):
        for i in range(n - r + 1):
            for j in range(m - c + 1):
                if check(r, c, sticker, i, j):
                    attach(r, c, sticker, i, j)
                    return
        # rotate
        sticker = list(map(list, zip(*sticker[::-1])))
        r, c = c, r
    return

 

위 두 함수를 종속하고 있으며, 각 스티커에 대해 이 함수가 한번씩 실행됩니다.

스티커의 크기와 배열을 이 곳에서 입력받습니다.

노트북 전체 범위에 대해 check() 함수로 붙일 수 없는지를 파악하고

가장 작은 행, 열부터 체크하므로 발견하는 즉시 모눈 종이를 붙이고 return해줍니다.

이때, 노트북 범위는 스티커를 붙일 너비와 높이를 고려하여 n - r, m - c까지로 해줍니다.

노트북 전체 범위를 체크했음에도 붙일 수 있는 곳이 없다면

시계방향으로 90도 회전하여 재확인을 해줍니다. 이 과정을 붙일 수 있는 곳을 찾을 때까지 3번 반복하여 줍니다.

회전하는 부분에 전치행렬을 활용했습니다. 시뮬레이션 문제에서 자주 활용되니 기억해두면 유용할 것입니다.

sticker = list(map(list, zip(*sticker[::-1])))

 

이렇게 4방향에 대해 모두 체크했음에도 붙일 수 있는 곳이 없다면 return하여 종료합니다.

 

 

전체코드

 

def check_and_attach():
    r, c = map(int, input().split())
    sticker = [list(map(int, input().split())) for _ in range(r)]
    for dir in range(4):
        for i in range(n - r + 1):
            for j in range(m - c + 1):
                if check(r, c, sticker, i, j):
                    attach(r, c, sticker, i, j)
                    return
        # rotate
        sticker = list(map(list, zip(*sticker[::-1])))
        r, c = c, r
    return

def check(r, c, sticker, start_x, start_y):
    for x in range(r):
        for y in range(c):
            if sticker[x][y] and graph[start_x + x][start_y + y]:
                return False
    return True

def attach(r, c, sticker, start_x, start_y):
    for i in range(r):
        for j in range(c):
            if sticker[i][j]:
                graph[i + start_x][j + start_y] = 1

n, m, k = map(int, input().split())
graph = [[0] * m for _ in range(n)]
for _ in range(k):
    check_and_attach()
result = 0
for i in range(n):
    result += sum(graph[i])
print(result)