https://www.acmicpc.net/problem/14500
14500번: 테트로미노폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변www.acmicpc.net
머리가 나쁘면 손이 고생한다.
1.가장 직관적인 풀이
모든 경우의수를 다 벡터에 넣고, 이를 반복하면서 구한다.
- 조금머리쓴거
잘 생각해보면 엿을(ㅗ) 을 제외한 모든 경우의 수는, 깊이가 4인 dfs이다.
따라서 각 점에 대하여 깊이가 4인 dfs의 최댓값을 구하고, 총 4방향의 가능한 엿에 대해 최댓값을 구한다.
- 조금더머리쓴거 (여기서부터는 다른사람코드를 참조했다)
좀 더 잘 생각해보면, 엿을 구하기 위해 따로 함수를 만들필요없이, dfs에 포함시킬 수 있다.
깊이가 2인 dfs에 대하여, 다음 지점을 방문처리만 하고, 현 지점에서 dfs를 진행한다면
ex)
깊이가 2인 상태
| Column 1 | Column 2 | Column 3 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 (현위치) | 0 |
| 0 | 0 | 0 |
방문처리만 하고 현위치에서 구함 (깊이 3)
| Column 1 | Column 2 | Column 3 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1(현위치) | 1 (방문처리) |
| 0 | 0 | 0 |
가능한경우
| Column 1 | Column 2 | Column 3 |
|---|---|---|
| 0 | 0 (가능) | 0 |
| 1 | 1(현위치) | 1 (방문처리) |
| 0 | 0 (가능) | 0 |
모든 엿모양을 구할 수 있다.
- 최적
3번에서 하나만 추가해주면 된다.
3번을 파이썬으로 구현하면 시간초과가 나고, pypy로 구현하면 2400초 정도가 걸린다.
이 시간을 줄이기 위해서 트릭을 쓴다.
먼져, 받은 arr의 최댓값을 max_val을 구해놓는다.
그리고, dfs를 수행하면서, v+(max_val * (4-depth)) 즉
현재의 값에서 앞으로 남은 기회가 모두 최댓값이여도 현재의 정답보다 작을 경우에, 바로 return시킨다.
이르면 200초대로 확 줄일 수 있다. 이런생각을 어케하는지 모르겠다.
4번코드
import sysinput =sys.stdin.readlinemoves=[(-1,0),(1,0),(0,-1),(0,1)]
def dfs(i,j,depth=1,v=0): global answer global max_val
if answer >= v+max_val*(4-depth): return if depth==4:
answer=max(answer,v) return for move in moves:
tmp_i= i+move[0] tmp_j= j+move[1]
if 0<=tmp_i<n and 0<=tmp_j<m and not visited[tmp_i][tmp_j]:
if depth==2: #볼록모양 visited[tmp_i][tmp_j]=True
dfs(i,j,depth+1,v+arr[tmp_i][tmp_j])
visited[tmp_i][tmp_j]=False
visited[tmp_i][tmp_j]=True
dfs(tmp_i,tmp_j,depth+1,v+arr[tmp_i][tmp_j])
visited[tmp_i][tmp_j]=False return
answer=0n,m=map(int,input().split())
arr=[[* map(int,input().split())]for _ in range(n)]max_val=max(map(max,arr))
visited=[[False for _ in range(m)]for _ in range(n)]for i in range(n):
for j in range(m): visited[i][j]=True dfs(i,j,1,v=arr[i][j])
visited[i][j]=Falseprint(answer)