문제
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
- 정사각형은 서로 겹치면 안 된다.
- 도형은 모두 연결되어 있어야 한다.
- 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.
아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.
문제 풀이
-
대칭, 회전으로 새겨날 수 있는 모든 경우에 대해서 완전탐색을 실시하였다. 모든 가능한 모양의 테트리스를 정의해두고 이를 완전탐색을 사용하여 풀이.
N, M = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(N)] # 테트로미노 회전, 대칭으로 나올 수 있는 모든 종류 tetromino_lst = [ [(0,0), (0,1), (0,2), (0,3)], [(0,0), (1,0), (2,0), (3,0)], [(0,0), (0,1), (1,0), (1,1)], [(0,0), (0,1), (0,2), (1,0)], [(1,0), (1,1), (1,2), (0,2)], [(0,0), (1,0), (1,1), (1,2)], [(0,0), (0,1), (0,2), (1,2)], [(0,0), (1,0), (2,0), (2,1)], [(2,0), (2,1), (1,1), (0,1)], [(0,0), (0,1), (1,0), (2,0)], [(0,0), (0,1), (1,1), (2,1)], [(0,0), (0,1), (0,2), (1,1)], [(1,0), (1,1), (1,2), (0,1)], [(0,0), (1,0), (2,0), (1,1)], [(1,0), (0,1), (1,1), (2,1)], [(1,0), (2,0), (0,1), (1,1)], [(0,0), (1,0), (1,1), (2,1)], [(1,0), (0,1), (1,1), (0,2)], [(0,0), (0,1), (1,1), (1,2)] ] max_v = 0 # 완전탐색으로 모든 점에서 테트로미노 별 합을 구하고 최대값과 비교 for x in range(N): for y in range(M): for tetromino in tetromino_lst: sum_v = 0 for dx, dy in tetromino: nx, ny = x + dx, y + dy if 0 <= nx < N and 0 <= ny < M: sum_v += arr[nx][ny] if sum_v > max_v: max_v = sum_v print(max_v)
-
DFS를 사용한 풀이 (1) → (python3 시간초과, pypy 통과)
모든 도형들이 4칸으로 이루어져 있고, 회전 및 대칭이 가능하기 때문에 보드판의 모든 정점에서부터 깊이를 4로 제한한 DFS를 돌릴 수 있다.
즉, 임의의 점에서부터 이미 방문한 점은 방문하지 않고 4칸을 움직여 가장 큰 수들을 밟는 방법이다.하지만 DFS 전략은 모든 도형이 한 붓 그리기 가 가능한 형태의 도형일 때만 가능하다.
"ㅗ" 모양의 블럭의 경우 모든 칸을 방문하려면 반드시 한 번은 뒤로 되돌아가서 이미 방문한 칸을 방문해야 하기 때문에 DFS 로 해결이 불가능하다.
따라서 DFS 전략을 쓰되, "ㅗ" 모양 블럭의 경우를 따로 처리해야 한다.def DFS(y, x, sum, depth): global answer if depth == 4: answer = max(answer, sum) return visit[y][x] = 1 # 중복 체크 for i in range(4): yy = y + dy[i] xx = x + dx[i] if 0 <= yy < n and 0 <= xx < m and visit[yy][xx] == 0: DFS(yy, xx, sum + arr[yy][xx], depth + 1) visit[y][x] = 0 # 다른 모양의 테트로미노를 확인할 때 잘못된 중복체크를 막기 def T(y, x): """ O X O O 위 그림처럼 X의 위치를 입력 받고 (y,x) 상,하,좌,우 중 하나만 제외시키고 좌표를 이동시키면, 회전가능한 "ㅗ" 모양의 모든 경우(4가지)를 구할 수 있다. """ global answer for k in range(4): sum = arr[y][x] check = 1 for i in range(4): if i == k: # 상하좌우 중 하나씩 제외시키기. continue yy = y + dy[i] xx = x + dx[i] if yy < 0 or xx < 0 or yy >= n or xx >= m: # 범위를 벗어나면 check = 0 break sum += arr[yy][xx] if check: answer = max(answer, sum) if __name__ == "__main__": answer = 0 n, m = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(n)] visit = [[0 for _ in range(m)] for _ in range(n)] dy = [0, 1, 0, -1] dx = [1, 0, -1, 0] for i in range(n): for j in range(m): DFS(i, j, 0, 0) T(i, j) print(answer)
-
DFS를 사용한 풀이 (2) → python3 통과
2번 풀이는 T를 구하는 함수를 따로 구현한 방법이다.
이 과정에서 시간이 더 드는 것 같아서 다른 방법을 구상한 결과 dfs 안에서 한 번에 "ㅗ" 모양을 탐색하는 코드를 발견하였다.def dfs(x, y, step, total): global answer if total + max_val * (4 - step) <= answer: # 이후의 층이 모두 최대값이어도 answer보다 작으면 break. return if step == 4: answer = max(answer, total) return for dx, dy in d: nx = x + dx ny = y + dy if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]: if step == 2: # "ㅗ" 모양 탐색 visited[nx][ny] = True dfs(x, y, step + 1, total + board[nx][ny]) visited[nx][ny] = False # 나머지 모양 탐색 visited[nx][ny] = True dfs(nx, ny, step + 1, total + board[nx][ny]) visited[nx][ny] = False if __name__ == "__main__": N, M = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(N)] max_val = max(map(max, board)) d = [(-1, 0), (0, -1), (1, 0), (0, 1)] visited = [[False] * M for _ in range(N)] answer = 0 for i in range(N): for j in range(M): visited[i][j] = True dfs(i, j, 1, board[i][j]) # 모든 칸에 대해서 검사 visited[i][j] = False print(answer) ```
