문제
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
정사각형은 서로 겹치면 안 된다.
도형은 모두 연결되어 있어야 한다.
정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.
아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.
입력
첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)
둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.
출력
첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.
초기 풀이
처음 문제를 봤을 때는 dx,dy로 5가지 도형을 표현해볼 수 있을지 고민했었는데 어떻게 구현을 한다하더라도 회전, 대칭을 표현할 수는 없어서 어떤 방법을 사용해야하나 고민하다가 DFS를 떠올렸다
DFS라면 이 다섯가지를 모두 표현할 수 있지 않나?라고 생각했었다
그래서 이 문제를 푸는데 오래걸렸다..
DFS로 풀되 카운트를 세서 카운트가 4가 되면 멈추도록 설계해서 합이 최대일 때 변수에 저장하도록 구현했다
다 됐다 생각했는데 마지막 테스트 케이스가 틀렸길래 이유를 고민하다가 ㅗ 모양은 DFS로 구현할 수 없다는 걸 새삼 깨달았고..
그럼 저 모양을 어떻게 카운트할까 생각했다 BFS를 썼어야했나? 그냥 완전 탐색으로 셀까? 생각하다가 다른 코드를 참고했다
완전 탐색으로 구현한 코드도 있었는데 분명 더 효율적으로 풀 방법이 있을 것 같아서 더 찾아보니 조금만 더 생각하면 DFS로 충분히 풀 수 있는 문제라는 걸 알게됐다
두 번째 블록에서 다음 블록으로 재귀호출을 하는게 아니라 두 번째 블록을 한 번 더 호출해서 남은 변을 더 탐색하고 합이 최대인지 확인한 후에 재귀 함수에서 빠져나와 다음 블록을 탐색하면 된다 ..
코드
import sys
n, m = map(int, sys.stdin.readline().split())
grid = []
for _ in range(n):
grid.append(list(map(int, sys.stdin.readline().split())))
dxs = [-1,1,0,0]
dys = [0,0,-1,1]
visited = [[False]*m for _ in range(n)]
# dfs를 사용하되 호출 횟수를 4번으로 제한(백트래킹)
def dfs(x, y, cnt, result):
global local_max
if cnt == 4:
local_max = max(local_max, result)
return
for dx, dy in zip(dxs, dys):
nx, ny = dx+x, dy+y
if -1<nx<n and -1<ny<m and not visited[nx][ny]:
if cnt == 2:
visited[nx][ny] = True
result += grid[nx][ny]
dfs(x, y, cnt+1, result)
visited[nx][ny] = False
result -= grid[nx][ny]
visited[nx][ny] = True
result += grid[nx][ny]
dfs(nx, ny, cnt+1, result)
visited[nx][ny] = False
result -= grid[nx][ny]
global_max = 0
for i in range(n):
for j in range(m):
local_max = 0
result = grid[i][j]
visited[i][j] = True
dfs(i, j, 1, result)
global_max = max(global_max, local_max)
visited[i][j] = False
print(global_max)사실 여기서도 result 변수를 계속 선언하기보다는 dfs 함수의 인자로 넣어주는게 더 깔끔한 코드이긴하다
