폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
- 정사각형은 서로 겹치면 안 된다.
- 도형은 모두 연결되어 있어야 한다.
- 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.
아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
# 코드 구현
(DFS)
모든 i,j에 대해서 dfs 를 진행하여 가능한 모든 경우의 수를 탐색함
idea1) cnt == 2 일때, 처음 block에 대해서 다시 dfs 를 진행함 * nx, ny <-> x, y 유의
이렇게 하지 않으면 매번 새로운 block에 대해서 4방 탐색을 진행하기 때문에 ㅗ,ㅏ,ㅓ,ㅜ 모양의 블록은 만들지 못함
idea2) max_val = max(map(max,arr)))를 통해서 2차원 배열의 최대값을 구한 후 max_n >= total + max_val * (4-cnt) 라면 return
>> 배열에 있는 가장큰 수를 다 포함해도 이전에 구했던 최대값이 크다면 return
>> 구현해주지 않으면 시간초과 !
*visited는 밖에 하나로 하여 visit == 1 -> dfs() -> visit == 0 으로 구현함
(2개의 for문안에 visit를 구현하여 문제를 틀렸었음)
|
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
|
import sys; input = sys.stdin.readline
a, b = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(a)]
visited = [[0]*b for _ in range(a)]
max_n = -1e9
dx = [-1,1,0,0]
dy = [0,0,-1,1]
max_val = max(map(max, graph))
def dfs(x,y,cnt,total):
global max_n,max_val
if max_n >= total + max_val*(4-cnt):
return
if cnt >= 4:
max_n = max(max_n,total)
return
else :
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < a and 0 <= ny < b :
if visited[nx][ny] == 0 :
if cnt == 2:
visited[nx][ny] = 1
dfs(x,y,cnt+1,total+graph[nx][ny])
visited[nx][ny] = 0
visited[nx][ny] = 1
dfs(nx,ny,cnt+1,total+graph[nx][ny])
visited[nx][ny] = 0
for i in range(a):
for j in range(b):
visited[i][j] = 1
dfs(i,j,1,graph[i][j])
visited[i][j] = 0
print(max_n)
|
cs |
# 느낀점
- 사소하게 신경써주어야 할 요소들이 많음