21277 짠돌이 호석

문제

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

21277번: 짠돌이 호석

 

접근

• 카카오 기출 문제 중 자물쇠와 열쇠 문제에서 힌트를 얻어, 기준 퍼즐1의 범위를 확장 시켜서 전체 경우마다 퍼즐2와 맞춰보는 식으로 풀이했다.
• 퍼즐의 크기 제한이 50 이므로 상하좌우 50씩 확장할 경우, 최대로 확장될 수 있는 퍼즐의 한 변의 길이는 150이다.
• 따라서 회전까지 고려했을 때 최대 4 * 100 * 100  * 50 * 50 = 10 * 9 번의 연산이 발생하므로 제한시간 2초 이내에 풀 수 있을 것
• 또한 퍼즐2를 회전시킬 때마다 r과 c가 변하므로 r과 c를 바꿔주는 작업을 해주어야 한다.

 

 

 

풀이

• 퍼즐1에 대해 상하좌우 50씩 확장시키고, 가능한 모든 경우에 대해 맞출 수 있는지 또한 맞출 수 있다면 그때의 크기가 얼마인지 계산한다.
• 퍼즐을 맞춘 결과를 구하는 것이 아니므로, 퍼즐을 맞췄다가 안되는 경우 다시 빼는 과정을 반복할 필요 없이 주어진 퍼즐이 맞출 수 있는 경우라면 x와 y의 최댓값과 최솟값만 계산해서 넓이를 구한다.

def rotate():
    global r, c

    res = [[0] * len(b) for _ in range(len(b[0]))]
    for i in range(len(b[0])):
        for j in range(len(b)):
            res[i][j] = b[j][len(b[0]) - i - 1]
    r, c = c, r
    return res


def match(x, y):
    global ans

    check = False
    for i in range(x, x + len(b)):
        for j in range(y, y + len(b[0])):
            if b[i - x][j - y] == 1 and board[i][j] == 1:
                check = True
                break
        if check:
            break

    if not check:
        min_x = min(x, 50)
        min_y = min(y, 50)
        max_x = max(x + r - 1, 50 + n - 1)
        max_y = max(y + c - 1, 50 + m - 1)

        s = (max_x - min_x + 1) * (max_y - min_y + 1)
        if ans == -1 or s < ans:
            ans = s


n, m = map(int, input().split())
a = [list(map(int, list(input()))) for _ in range(n)]

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

board = [[0] * (m + 2 * 50) for _ in range(n + 2 * 50)]
for i in range(50, 50 + n):
    for j in range(50, 50 + m):
        board[i][j] = a[i - 50][j - 50]

ans = -1
for _ in range(4):
    b = rotate()
    for i in range(50 + n):
        for j in range(50 + m):
            match(i, j)

print(ans)