문제이해
문제를 보면 테트로미노의 정의가 나와있다.
정사각형은 서로 겹치면 안 된다.
도형은 모두 연결되어 있어야 한다.
정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
그리고 5개의 도형 사진이 있다. 이 도형들을 상하좌우반전 또는 회전으로 변경할 수 있다고 한다.
이렇게 됐을 때 크기가 N*M인 종이 위에 테트로미노 하나를 놓으려고 한다.
종이에는 각각 숫자가 적혀있다.
테트로미노 하나를 놓아서 숫자들의 합이 가장 클때의 숫자들의 합을 출력해라
문제 접근
문제를 딱 봤을 때 완전탐색 문제라고 생각했고 2가지로 나누어 접근할 수 있었다.
1. 도형을 돌리거나 조작해서 여러개의 도형으로 만드는 것.
2. 도형을 종이위에 두고 합을 구하는 것.
따라서 도형 하나를 예시로 돌려보면서 생각했다. 그렇게 패턴이 나왔고 다른 도형들에게도 적용할 수 있겠다고 생각했다.
polio[1] = [[0,0],[1,0],[2,0],[2,1]]
# 오른쪽으로 회전하면 [[0,0],[0,1],[0,2],[1,2]] 안에 값이 swap됨
# 왼쪽으로 회전하면 [[0,0],[0,-1],[0,-2],[-1,-2]] 안에값 스왑하고 -붙임
# 180도 회전하면 [[0,0],[-1,0],[-2,0],[-2,-1]]됨 -만 붙임
# 좌우 반전하면 [[0,0],[1,0],[2,0],[2,-1]]
# 상하 반전하면 [[0,0],[-1,0],[-2,0],[-2,1]]이다.이렇게 도형을 돌리는 부함수를 만들어서 도형을 돌리고 리스트에 저장했다.
def turn(polio):
for i in range(5):
a, b, c, d, e, f, g, h = polio[i][0][0],polio[i][0][1],polio[i][1][0],polio[i][1][1],polio[i][2][0],polio[i][2][1],polio[i][3][0],polio[i][3][1]
polio.append([[b,a],[d,c],[f,e],[h,g]])
polio.append([[-b,-a],[-d,-c],[-f,-e],[-h,-g]])
polio.append([[-a,-b],[-c,-d],[-e,-f],[-g,-h]])
polio.append([[-a,b],[-c,d],[-e,f],[-g,h]])
polio.append([[a,-b],[c,-d],[e,-f],[g,-h]])
polio.append([[b,-a],[d,-c],[f,-e],[h,-g]])
polio.append([[-b,a],[-d,c],[-f,e],[-h,g]])다음으로는 종이 위의 값들을 합하고 비교하는 함수를 만들었다.
def go(x, y):
global answer
for pol in polio:
four = []
count = 0
for i in range(4):
four.append([x+pol[i][0], y+pol[i][1]])
for one in four:
if one[0]<0 or one[1]<0 or one[0]>N-1 or one[1]>M-1:
break
count += pan[one[0]][one[1]]
if count > answer:
answer = count마지막으로 go(x,y)에 N, M까지의 좌표들을 한번씩 넣어주면 종이 위의 모든 곳에 도형을 두고 비교하는 것과 같다.
제출 코드
import sys
N, M = map(int, sys.stdin.readline().split())
pan = []
for i in range(N):
pan.append(list(map(int, sys.stdin.readline().split())))
# 완전탐색
polio = [[[0,0],[0,1],[0,2],[0,3]],[[0,0],[1,0],[2,0],[2,1]],[[0,0],[0,1],
[1,0],[1,1]],[[0,0],[1,0],[1,1],[2,1]],[[0,0],[0,1],[0,2],[1,1]]]
# -> 오른쪽으로 회전하면 [[0,0],[0,1],[0,2],[1,2]] 안에 값이 swap됨
# 왼쪽으로 회전하면 [[0,0],[0,-1],[0,-2],[-1,-2]] 안에값 스왑하고 -붙임
# 180도 회전하면 [[0,0],[-1,0],[-2,0],[-2,-1]]됨 -만 붙임
# 좌우 반전하면 [[0,0],[1,0],[2,0],[2,-1]]
# 상하 반전하면 [[0,0],[-1,0],[-2,0],[-2,1]]이다.
#도형 돌려보기
def turn(polio):
for i in range(5):
a, b, c, d, e, f, g, h = polio[i][0][0],polio[i][0][1],polio[i][1][0],polio[i][1][1],polio[i][2][0],polio[i][2][1],polio[i][3][0],polio[i][3][1]
polio.append([[b,a],[d,c],[f,e],[h,g]])
polio.append([[-b,-a],[-d,-c],[-f,-e],[-h,-g]])
polio.append([[-a,-b],[-c,-d],[-e,-f],[-g,-h]])
polio.append([[-a,b],[-c,d],[-e,f],[-g,h]])
polio.append([[a,-b],[c,-d],[e,-f],[g,-h]])
polio.append([[b,-a],[d,-c],[f,-e],[h,-g]])
polio.append([[-b,a],[-d,c],[-f,e],[-h,g]])
def go(x, y):
global answer
for pol in polio:
four = []
count = 0
for i in range(4):
four.append([x+pol[i][0], y+pol[i][1]])
for one in four:
if one[0]<0 or one[1]<0 or one[0]>N-1 or one[1]>M-1:
break
count += pan[one[0]][one[1]]
if count > answer:
answer = count
answer = 0
turn(polio)
for x in range(N):
for y in range(M):
go(x,y)
print(answer)
