반응형
https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
import sys
ssr = sys.stdin.readline
def sol1(r,c):#o
global n,m
dp = [(0,1),(1,0),(1,1)]
result = t[r][c]
for i in dp:
if 0 <= r+i[0] < n and 0 <= c+i[1] < m:
result += t[r+i[0]][c+i[1]]
else:
return 0
return result
def sol2(r,c):#i1
global n,m
dp = [(0,1),(0,2),(0,3)]
result = t[r][c]
for i in dp:
if 0 <= r+i[0] < n and 0 <= c+i[1] < m:
result += t[r+i[0]][c+i[1]]
else:
return 0
return result
def sol3(r,c):#i2
global n,m
dp = [(1,0),(2,0),(3,0)]
result = t[r][c]
for i in dp:
if 0 <= r+i[0] < n and 0 <= c+i[1] < m:
result += t[r+i[0]][c+i[1]]
else:
return 0
return result
def sol4(r,c):#t1
global n,m
dp = [(0,-1),(-1,0),(0,1)]
result = t[r][c]
for i in dp:
if 0 <= r+i[0] < n and 0 <= c+i[1] < m:
result += t[r+i[0]][c+i[1]]
else:
return 0
return result
def sol5(r,c):#t2
global n,m
dp = [(-1,0),(0,1),(1,0)]
result = t[r][c]
for i in dp:
if 0 <= r+i[0] < n and 0 <= c+i[1] < m:
result += t[r+i[0]][c+i[1]]
else:
return 0
return result
def sol6(r,c):#t3
global n,m
dp = [(0,-1),(1,0),(0,1)]
result = t[r][c]
for i in dp:
if 0 <= r+i[0] < n and 0 <= c+i[1] < m:
result += t[r+i[0]][c+i[1]]
else:
return 0
return result
def sol7(r,c):#t4
global n,m
dp = [(-1,0),(0,-1),(1,0)]
result = t[r][c]
for i in dp:
if 0 <= r+i[0] < n and 0 <= c+i[1] < m:
result += t[r+i[0]][c+i[1]]
else:
return 0
return result
def sol8(r,c):#l1
global n,m
dp = [(1,0),(2,0),(2,1)]
result = t[r][c]
for i in dp:
if 0 <= r+i[0] < n and 0 <= c+i[1] < m:
result += t[r+i[0]][c+i[1]]
else:
return 0
return result
def sol9(r,c):#l2
global n,m
dp = [(0,-1),(0,-2),(1,-2)]
result = t[r][c]
for i in dp:
if 0 <= r+i[0] < n and 0 <= c+i[1] < m:
result += t[r+i[0]][c+i[1]]
else:
return 0
return result
def sol10(r,c):#l3
global n,m
dp = [(-1,0),(-2,0),(-2,-1)]
result = t[r][c]
for i in dp:
if 0 <= r+i[0] < n and 0 <= c+i[1] < m:
result += t[r+i[0]][c+i[1]]
else:
return 0
return result
def sol11(r,c):#l4
global n,m
dp = [(0,1),(0,2),(-1,2)]
result = t[r][c]
for i in dp:
if 0 <= r+i[0] < n and 0 <= c+i[1] < m:
result += t[r+i[0]][c+i[1]]
else:
return 0
return result
def sol12(r,c):#j1
global n,m
dp = [(1,0),(2,0),(2,-1)]
result = t[r][c]
for i in dp:
if 0 <= r+i[0] < n and 0 <= c+i[1] < m:
result += t[r+i[0]][c+i[1]]
else:
return 0
return result
def sol13(r,c):#j2
global n,m
dp = [(0,-1),(0,-2),(-1,-2)]
result = t[r][c]
for i in dp:
if 0 <= r+i[0] < n and 0 <= c+i[1] < m:
result += t[r+i[0]][c+i[1]]
else:
return 0
return result
def sol14(r,c):#j3
global n,m
dp = [(-1,0),(-2,0),(-2,1)]
result = t[r][c]
for i in dp:
if 0 <= r+i[0] < n and 0 <= c+i[1] < m:
result += t[r+i[0]][c+i[1]]
else:
return 0
return result
def sol15(r,c):#j4
global n,m
dp = [(0,1),(0,2),(1,2)]
result = t[r][c]
for i in dp:
if 0 <= r+i[0] < n and 0 <= c+i[1] < m:
result += t[r+i[0]][c+i[1]]
else:
return 0
return result
def sol16(r,c):#s1
global n,m
dp = [(0,1),(-1,1),(-1,2)]
result = t[r][c]
for i in dp:
if 0 <= r+i[0] < n and 0 <= c+i[1] < m:
result += t[r+i[0]][c+i[1]]
else:
return 0
return result
def sol17(r,c):#s2
global n,m
dp = [(1,0),(1,1),(2,1)]
result = t[r][c]
for i in dp:
if 0 <= r+i[0] < n and 0 <= c+i[1] < m:
result += t[r+i[0]][c+i[1]]
else:
return 0
return result
def sol18(r,c):#z1
global n,m
dp = [(0,1),(1,1),(1,2)]
result = t[r][c]
for i in dp:
if 0 <= r+i[0] < n and 0 <= c+i[1] < m:
result += t[r+i[0]][c+i[1]]
else:
return 0
return result
def sol19(r,c):#z2
global n,m
dp = [(1,0),(1,-1),(2,-1)]
result = t[r][c]
for i in dp:
if 0 <= r+i[0] < n and 0 <= c+i[1] < m:
result += t[r+i[0]][c+i[1]]
else:
return 0
return result
n,m = map(int, ssr().split())
t = [list(map(int, ssr().split())) for _ in range(n)]
ans = []
for i in range(n):
for j in range(m):
ans.append(sol1(i,j))
ans.append(sol2(i,j))
ans.append(sol3(i,j))
ans.append(sol4(i,j))
ans.append(sol5(i,j))
ans.append(sol6(i,j))
ans.append(sol7(i,j))
ans.append(sol8(i,j))
ans.append(sol9(i,j))
ans.append(sol10(i,j))
ans.append(sol11(i,j))
ans.append(sol12(i,j))
ans.append(sol13(i,j))
ans.append(sol14(i,j))
ans.append(sol15(i,j))
ans.append(sol16(i,j))
ans.append(sol17(i,j))
ans.append(sol18(i,j))
ans.append(sol19(i,j))
print(max(set(ans)))오늘 코드는 보여드리기 상당히 죄송한 수준입니다. 구현 난이도가 어려운 문제는 아닌데 이걸 어떻게 효율을 살릴 수 있을지 모르겠더라구요. 코드 자체를 짧게 쓰는거야 얼마든지 하겠지만 가독성이 떨어질테고, 코드가 짧다고 해서 시간이 덜 걸리는 코드는 또 아니거든요. 다음에 다른 분들 코드를 보면서 어떻게 하면 효율적으로 짤 수 있을지 고민을 해봐야겠습니다. 일단 이번 포스팅은 위의 코드를 기준으로 설명을 드리겠으니 약간 불편하더라도 이해해주시면 감사하겠습니다.
문제 접근은 그래프 탐색과 브루트 포스입니다. 문제 자체는 딱 보자마자 아 브루트 포스구나, 테트리스니까 이차원배열 탐색하겠구나 하고 바로 감이 오는 문제입니다. 거기다 문제가 요구하는 것도 조건에 맞게 4개를 방문하고 그 중 최대값을 출력해달라는 것이라 구현 난이도도 쉽습니다. 그래서 저는 모든 경우(회전을 고려하여 테트로미노가 중복되지 않는 모양으로 존재할 수 있는 모든 경우)에 대한 탐색 함수를 정의하고, 2중 반복문에서 모든 좌표를 돌면서 모든 탐색함수를 실행하고 ans에 결과를 저장한다음 그 중 max를 출력하는 방법을 이용했습니다(set으로 중복된 값들을 지워서 max에서 시간 복잡도를 조금 줄여보려고 했습니다). 아마 풀이를 찾으시는 분들 대부분이 좀 짧고 가독성이 좋은 코드가 없나 싶어서 찾아보실 것 같은데 이런 흉물스러운 걸 보여드려서 죄송하네요.
반응형
'Problem Solving > BOJ' 카테고리의 다른 글
| [BOJ][Python]9019번 풀이 (0) | 2022.07.14 |
|---|---|
| [BOJ][Python]16928번 풀이 (0) | 2022.07.13 |
| [BOJ][Python]2491번 풀이 (0) | 2022.07.11 |
| [BOJ][Python]10026번 풀이 (0) | 2022.07.11 |