https://www.acmicpc.net/problem/14500
접근
- 모든 좌표에서 dfs 탐색해서 테트로미노를 구한다.
- 폴리오미노가 2개일 때 3번째 폴리오미노를 더하고 2번째 좌표에서 다시 탐색해서
ㅗ, ㅏ, ㅓ, ㅜ
테트로미노를 구한다.
풀이
from sys import stdin
def dfs(depth, total, r, c):
global res
if res >= total + (4 - depth) * max_num: # (1)
return
if depth == 4: # (2)
res = max(res, total)
return
for i in range(4):
nr, nc = r + direction[i], c + direction[3 - i]
if is_out_of_range(nr, nc) or visited[nr][nc]:
continue
if depth == 2: # (3)
visited[nr][nc] = True
dfs(depth + 1, total + board[nr][nc], r, c)
visited[nr][nc] = False
visited[nr][nc] = True
dfs(depth + 1, total + board[nr][nc], nr, nc)
visited[nr][nc] = False
def is_out_of_range(r, c):
return r < 0 or r >= n or c < 0 or c >= m
n, m = map(int, stdin.readline().split())
board = [list(map(int, stdin.readline().split())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]
direction = [1, 0, -1, 0]
res = 0
max_num = max(map(max, board))
for r in range(n):
for c in range(m):
visited[r][c] = True
dfs(1, board[r][c], r, c)
visited[r][c] = False
print(res)
- (1) 남은 폴리오미노를 board의 가장 큰 값에 놓아도 최댓값을 갱신할 수 없을 경우 백트래킹한다.
- (2) 폴리오미노 4개를 모두 탐색했을 경우 최댓값을 갱신한다.
- (3) 현재 폴리오미노가 2개일 때 3번째 폴리오미노를 더한 상태에서 r, c 좌표로 다시 dfs 탐색한다.
예를 들어◻︎◻︎
상태에서 3번째 폴리오미노를 더해◻︎◻︎◻︎
가 되면◻︎◼︎◻︎
의 색칠된 폴리오미노에서 다음 폴리오미노를 탐색한다. 이 때는ㅗ, ㅜ
테트로미노를 찾을 수 있게 된다.