문제
아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.
문제 정리
테트로미노를 단 하나만 적절히 놓아서 최대값을 구해야한다.테트로미노는 회전, 이동이 가능하다.- 한 점을 기준으로 하여 모든 도형(19개)을 조건에 통과되는지 대입한다.
- 조건 : 해당
테트로미노를 놓을 수 있는가?(그래프 범위를 벗어나지 않는가?)
한 점에서 이동할 모든 경우의 수..즉, 사실 각기 다른점을 4번 방문 가능한가? 이 문제로 볼 수 있다(dfs, bfs) 이후 풀이하다가 알게 됐지만 여기에는 함정이 있었다.
문제 풀이
첫번째 풀이
먼저 dfs로 접근을 했다. 최근 recursion을 연습하고 있었기에 좋은 접근이였다.
하지만 문제의 마지막 테스트 케이스를 통과하지 못했다. 하여 왜 그런지 살펴보았는데 凸 도형은 dfs로 탐색하는 것이 불가능 했다. 때문에 凸 도형만 따로 처리를 하여 코드를 작성했다.
# 점을 입력받고 해당 점을 통해 만들어질 수 있는 테트로미노 중 가장 최대값을 찾기
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
# 凸 도형을 제외한 나머지 도형을 그래프에 놓기
def make_other(start, m, n, cnt, value, graph, visited):
# 종료 조건 : 그래프에 4번 방문했다면
if cnt == 4:
return value # 해당 값 반환
max_value = 0
x, y = start
moves = [(-1, 0), (0, -1), (1, 0), (0, 1)] # 움직이는 방향 좌상우하
# 현재 위치에서 움직일 위치를 더해 새로운 위치로 변환
for dx, dy in moves:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
visited[nx][ny] = True # 방문처리
max_value = max(max_value, make_other((nx, ny), m, n, cnt + 1, value + graph[nx][ny], graph, visited))
visited[nx][ny] = False
else:
break # 그래프 범위 밖이라면 바로 break(가지치기)
return max_value
# 예외처리 ㅗ 도형은 따로 탐색하는 로직을 만들어야함.
# 한점에서 시작하여 좌측, 우측, 상단, 하단의 세 점을 방문해야한다.
def make_ㅗ(start, m, n, graph):
max_value = 0
x, y = start
# 상하우좌
moves = [[(0,-1),(-1,-1),(1,-1)],[(0,1),(-1,1),(1,1)],[(1,0),(1,-1),(1,1)],[(-1,0),(-1,-1),(-1,1)]]
# 시작점에서부터 ㅗ도형을 방향전환하며 그리기
for move in moves:
value = graph[x][y]
for dx,dy in move:
nx, ny = x+dx, y+dy
if 0 <= nx < n and 0 <= ny < m:
value += graph[nx][ny]
else:
break
max_value = max(max_value, value)
return max_value
# 각 점에 해당되는 최대값중 가장 최대값을 찾기
max_value = 0
for i in range(n):
for j in range(m):
# start는 방문하고 시작해야함.
visited = [[False] * m for _ in range(n)]
visited[i][j] = True
max_value = max(max_value,make_other((i,j), m, n, 1, graph[i][j], graph, visited),make_ㅗ((i,j), m, n, graph))
print(max_value)전체적인 로직은 이렇다
1. 입력된 점을 기준으로 하여 凸을 제외한 나머지 도형은 dfs로 탐색
2. 凸 도형은 방문하는 점 당 ㅓ ㅏ ㅗ ㅜ를 한 번씩 탐색
하지만 시간초과가 났다.
때문에 dfs를 과감히 버리고 모든 경우의 수에 대해 생각해보았다.
두번째 풀이
그러면 아래와 같은 경우의 수가 나오게 된다. 즉 총 19가지의 경우의 수이다.
def calculate_tetris(x, y, n, m, graph, moves):
max_value = 0
for move in moves:
value = 0
for dx, dy in move:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m:
value += graph[nx][ny]
else: # 그래프 범위에서 벗어난다면 break(가지치기)
break
else:
max_value = max(max_value, value)
return max_value
# 모든 점에 대해 모든 경우의 수를 탐색
def make_tetris(n, m, graph):
moves=[[(0,0),(0,1),(0,2),(0,3)],\
[(0,0),(1,0),(2,0),(3,0)],\
[(0,0),(1,0),(0,1),(1,1)],\
[(0,0),(1,0),(2,0),(2,1)],\
[(0,1),(1,1),(2,1),(2,0)],\
[(0,0),(0,1),(1,1),(2,1)],\
[(0,0),(0,1),(1,0),(2,0)],\
[(0,0),(1,0),(1,1),(1,2)],\
[(0,2),(1,1),(1,2),(1,0)],\
[(0,0),(0,1),(0,2),(1,2)],\
[(0,0),(1,0),(0,1),(0,2)],\
[(0,0),(1,0),(1,1),(2,1)],\
[(0,1),(1,1),(1,0),(2,0)],\
[(1,0),(1,1),(0,1),(0,2)],\
[(0,0),(0,1),(1,1),(1,2)],\
[(0,1),(1,0),(1,1),(1,2)],\
[(0,0),(0,1),(0,2),(1,1)],\
[(0,0),(1,0),(1,1),(2,0)],\
[(0,1),(1,1),(1,0),(2,1)]]
max_value = 0
# 그래프의 모든 점 방문
for i in range(n):
for j in range(m):
max_value = max(max_value, calculate_tetris(i, j, n, m, graph, moves))
return max_value
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
print(make_tetris(n, m, graph))그래프의 모든 점에 대해서 19가지의 도형을 대입하고 범위에 벗어난다면 break를 통해 시간초과를 피하는 방향으로 구현했다.
풀이 후기
구현은 쉬웠지만 시간초과로 인해 통과하지 못함이 힘들었다.
종류가 몇 개 없다면 문제 자체에서 이렇게 경우의 수를 다 구하라고 말하는 것 같기도 하다.
dfs로 조건을 추가해서 푸는 방법 또한 고려해야할 듯 싶다.
