Algorithm 문제
[백준] 14500 - 테트로미노
노예2
2019. 7. 15. 21:23
https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누
www.acmicpc.net
Brute Force 문제
다른 분들 풀이를 보면 본래 의도는 블록을 하나씩 붙여가며 dfs 하는 문제로 보입니다.
(ㅜ 형태의 블록을 제외하고는 dfs, 해당 블록은 예외처리로 계산한다고 함..)
전 모든 블록의 회전, 반전 경우를 구하고 모든 위치에서 합을 계산했습니다...
python3로는 통과가 안되어 pypy2로 제출...
<pypy2 코드>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
import sys
# 시계방향으로 90도 회전
def rotate_quad(block):
first = []
for i in range(len(block[0])):
t = []
for j in range(len(block)-1, -1, -1):
t.append(block[j][i])
first.append(t)
return first
# 지정 횟수만큼 회전
def rotate(block, num):
re = [block]
temp = block
for _ in range(num):
temp = rotate_quad(temp)
re.append(temp)
return re
# 대칭
def inverse(block):
re = []
for l in block:
re.append(list(reversed(l)))
return re
# 기본 블록 형태. 백준 site 참고
blocks = [
[[1, 1, 1, 1]],
[[1, 1], [1, 1]],
[[1, 0, 0], [1, 1, 1]],
[[1, 1, 0], [0, 1, 1]],
[[1, 1, 1], [0, 1, 0]]
]
# 반전, 회전시 동일한 블록 제외 위해 아래의 두 리스트를 설정
# 순서대로 반전 여부
inverses = [False, False, True, True, False]
# 순서대로 회전 횟수
rotates = [1, 0, 3, 1, 3]
lines = sys.stdin.readlines()
n, m = tuple(map(int, lines[0].split()))
paper = [list(map(int, line.split())) for line in lines[1:]]
re = 0
for block, inv, rot in zip(blocks, inverses, rotates):
rot_inv = rotate(block, rot)
if inv:
rot_inv += rotate(inverse(block), rot)
for case in rot_inv:
# 블록을 위치시킬 수 있는 범위 내에서
for i in range(n+1-len(case)):
for j in range(m+1-len(case[0])):
# 합을 계산
tmp = 0
for y in range(len(case)):
for x in range(len(case[0])):
tmp += case[y][x] * paper[i+y][j+x]
re = max(re, tmp)
sys.stdout.write(str(re))
|
cs |