[Python/파이썬] 백준 21277번 짠돌이 호석

21277번: 짠돌이 호석

 

코드

n1, m1 = map(int, input().split())
board1 = [list(input()) for _ in range(n1)]
n2, m2 = map(int, input().split())
board2 = [list(input()) for _ in range(n2)]


def rotate(b):  # 시계방향 90도 회전
    global n2, m2
    new_b = [[None]*len(b) for _ in range(len(b[0]))]
    for i in range(len(b)):
        for j in range(len(b[0])):
            new_b[j][len(b)-1-i] = b[i][j]
    n2, m2 = len(new_b), len(new_b[0])
    return new_b


# bb에 board1은 고정시켜놓고, board2를 90도씩 돌려서 옮기며 비교
bb = [[0]*151 for _ in range(151)]

# bb에 (50, 50)부터 board1 고정
for i in range(50, 50+n1):
    for j in range(50, 50+m1):
        bb[i][j] = board1[i-50][j-50]

ans = 10000
for d in range(4):  # 방향
    for i in range(50-n2, 50+n1+1):  # board2의 시작 행
        for j in range(50-m2, 50+m1+1):  # board2의 시작 열
            # i, j를 왼쪽 아래로 하는 board2가 board1과 겹치는지?
            possible = True
            for r in range(i, i+n2):
                for c in range(j, j+m2):
                    if bb[r][c] == '1' and board2[r-i][c-j] == '1':
                        possible = False
                        break
                if not possible:
                    break
            if possible:
                x1 = min(i, 50)
                y1 = min(j, 50)
                x2 = max(i+n2-1, 49+n1)
                y2 = max(j+m2-1, 49+m1)
                area = (x2-x1+1)*(y2-y1+1)
                if area < ans:
                    ans = area
    board2 = rotate(board2)


print(ans)

 

2개의 퍼즐을 모두 돌릴 필요없이 하나의 퍼즐은 고정시켜놓고, 다른 하나를 90도씩 돌리며 비교하면 된다. 이렇게 하면 중간의 3중 반복문도 최대 4*100*100=40,000번의 연산만 하면 되므로 시간 초과 없이 통과할 수 있다.

 

풀이는 3개의 파트로 나눌 수 있다.

1. rotate()

퍼즐을 시계방향으로 90도 회전시켜주는 함수이다. 퍼즐의 행 길이와, 열 길이인 n2, m2도 바꿔준다.

 

2. bb에 board1 고정

board1을 기준으로 잡기 위해 bb의 (50, 50)을 시작점으로 하여 board1을 고정시킨다.

 

3. board2를 90도씩 돌리며 4방향 비교

board1의 대각선 왼쪽 아래부터 대각선 오른쪽 위까지 board2를 한 칸씩 이동시키며 퍼즐이 안 겹치게 하나의 액자에 담을 수 있는지 알아본다. 담을 수 있는 경우에는 그때의 액자 크기를 계산하여 최소인지 알아본다. 대각선 왼쪽 아래부터 오른쪽 위까지 모두 비교했다면 rotate 함수를 이용하여 board2를 돌려서 다시 비교한다.