백준 21277 짠돌이 호석 (파이썬)

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

21277번: 짠돌이 호석

풀이

구현 문제이다. 그러나 회전한다는 점을 생각하는게 까다로웠다. 그러나 풀이 자체는 그리 어려운 편이 아니다.

아래의 글을 참고하여 풀었다.

https://ongveloper.tistory.com/526

백준 21277 짠돌이 호석 Kotlin (완전탐색)

즉 두개의 퍼즐을 각각 따로따로 한번씩 비교하는 것이 아니라 하나의 큰 판에 퍼즐을 박아두고 다른 하나를 올려보며 비교하는 식이다.

그리고 개인적으로는 비교 하는 로직을 작성하는게 문제의 주된 포인트라고 생각한다. 그렇기에 참고한 블로그의 방법처럼 회전하는 퍼즐을 미리 모두 구해 문제를 풀었다.

코드

import sys

input = lambda: sys.stdin.readline().rstrip()

def simulate(i, j, pzl):
    n2 = len(pzl)
    m2 = len(pzl[0])

    for r in range(n2):
        for c in range(m2):
            if (puzzle1[i + r][j + c] & pzl[r][c]) == 1:
                return 10001

    minR = min(i, 50)
    maxR = max(50 + N1, i + n2)
    minC = min(j, 50)
    maxC = max(50 + M1, j + m2)

    return (maxR - minR) * (maxC - minC)


N1, M1 = map(int, input().split(" "))
puzzle1 = [[0] * 150 for _ in range(150)]

for i in range(N1):
    line = input()
    for j, value in enumerate(line):
        puzzle1[50 + i][50 + j] = int(value)

N2, M2 = map(int, input().split(" "))
temp = [list(map(int, input())) for _ in range(N2)]

puzzle2 = [
    [[temp[r][c] for c in range(M2)] for r in range(N2)],
    [[temp[N2 - c - 1][r] for c in range(N2)] for r in range(M2)],
    [[temp[N2 - r - 1][M2 - c - 1] for c in range(M2)] for r in range(N2)],
    [[temp[c][M2 - r - 1] for c in range(N2)] for r in range(M2)]
]

answer = 10001

for r in range(101):
    for c in range(101):
        for pzl in puzzle2:
            answer = min(answer, simulate(r, c, pzl))

print(answer)

아직 갈 길이 멀다