[Python] 백준 14500번 테트로미노
안녕하세요 :-)
요즘 날씨가 미친 듯이 덥네요 ㅜ
오늘은 삼성 SW 역량 테스트 기출문제 14500번 테트로미노를 풀어보았습니다.
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
이번 문제는 별도의 규칙이 없는 것을 보니,
가능한 경우를 모두 확인해봐야 하는 brute force 문제입니다!
우선 5가지의 테트로미노를 case별로 나눠서 좌표를 생각해보도록 하겠습니다.
테트로미노는 임의로 1~5번까지 순서를 매겼습니다.
그리고 가장 왼쪽이면서 위쪽에 있는 정사각형의 좌표값을 (0, 0)이라고 가정하였습니다.
우선 1번 테트로미노입니다.
1번의 경우에는 회전이나 대칭을 시켰을 때 위와 같은 2가지 케이스가 나오게 됩니다.
다른 정사각형의 좌표값은 위의 사진과 같습니다.
다음으로는 2번 테트로미노입니다.
2번 테트로미노는 정사각형의 형태이기 때문에
회전이나 대칭을 시켰을 때 1가지 케이스 밖에 나오지 않습니다.
3번 테트로미노입니다.
3번 테트로미노의 경우에는 기존 문제에서 제공하는 3번 테트로미노 이미지를 회전시켰을 때의 케이스 4개와
기존 테트로미노를 대칭 시킨 후 회전시켰을 때의 케이스 4개를 합쳐 총 8가지가 존재합니다.
이번에는 4번 테트로미노입니다.
4번 테트로미노는 기존 이미지를 회전 시켰을 때와
대칭시킨 후 회전시켰을 때의 경우를 합쳐 총 4가지가 존재합니다.
마지막으로 5번 테트로미노입니다.
5번 테트로미노 역시 4번과 마찬가지로 회전시켰을 때의 케이스 2개와
대칭시킨 후 회전시켰을 때의 케이스를 합쳐 총 4가지가 존재합니다.
5가지의 테트로미노를 가지고 만들 수 있는 케이스를 모두 구했으니 (총 19가지)
테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 구하면 됩니다.
아래는 제가 구현한 코드입니다!
n, m = map(int, input().split())
paper = [list(map(int, input().split())) for _ in range(n)]
max = 0
# 테트로미노 좌표 정보 (기준점은 가장 왼쪽 + 위쪽에 위치한 정사각형)
case = [
# case 1
[[0, 0], [0, 1], [0, 2], [0, 3]],
[[0, 0], [1, 0], [2, 0], [3, 0]],
# case 2
[[0, 0], [0, 1], [1, 0], [1, 1]],
# case 3
[[0, 0], [1, 0], [2, 0], [2, 1]],
[[0, 0], [1, 0], [0, 1], [0, 2]],
[[0, 0], [0, 1], [1, 1], [2, 1]],
[[0, 0], [0, 1], [0, 2], [-1, 2]],
[[0, 0], [0, 1], [-1, 1], [-2, 1]],
[[0, 0], [1, 0], [1, 1], [1, 2]],
[[0, 0], [0, 1], [1, 0], [2, 0]],
[[0, 0], [0, 1], [0, 2], [1, 2]],
# case 4
[[0, 0], [1, 0], [1, 1], [2, 1]],
[[0, 0], [0, 1], [-1, 1], [-1, 2]],
[[0, 0], [0, 1], [-1, 1], [1, 0]],
[[0, 0], [0, 1], [1, 1], [1, 2]],
# case 5
[[0, 0], [0, 1], [0, 2], [1, 1]],
[[0, 0], [-1, 1], [0, 1], [1, 1]],
[[0, 0], [0, 1], [0, 2], [-1, 1]],
[[0, 0], [1, 0], [2, 0], [1, 1]]
]
# max 값 확인 후 update
def check(sum):
global max
if sum > max:
max = sum
# 테트로미노가 놓인 칸에 쓰여 있는 수들의 합 구하기
def tetromino(i, j):
for x in range(19):
sum = 0
for y in range(4):
try:
sum += paper[i+case[x][y][0]][j+case[x][y][1]]
except:
break
check(sum)
for i in range(n):
for j in range(m):
tetromino(i, j)
print(max)저는 위에서 구했던 테트로미노의 케이스를 case라는 3차원 배열에 담아 사용하였습니다.
이후 구하고자 하는 기준점의 x, y 좌표에 테트로미노의 위치 좌표값을 더해주었습니다.
예를 들어, (1, 3) 좌표에서의 테트로미노 1번을 체크하는 경우에는
위의 사진과 같이 구한다고 생각하면 됩니다.
추가로 주의해야할 점은 체크하는 좌표값을 기준점으로 잡았을 때,
index out of bound가 발생할 수 있기 때문에
try/except 구문을 활용해주었습니다.
모든 케이스와 좌표값을 구하는 것이 조금 귀찮긴 했는데,
문제 자체는 굉장히 쉬웠던 것 같습니다!