[백준 14500] 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

https://www.acmicpc.net/problem/14500

Tip

•

도형의 회전과 대칭함수를 구현하여 모든 경우의 수를 따져가며 종이를 완전탐색할 순 있지만,,

→ DFS로 접근하는 것이 훨씬 간편!

DFS(깊이 우선 탐색)?

•

테트로미노는 정사각형을 4개를 이어 붙인 도형이므로,
시작 위치의 count값을 1로 했을 때, count가 4가 될 때까지 탐색을 수행한 경로로 표현 가능

◦

단, ㅜ ㅗ ㅓ ㅏ 모양은 일반적인 DFS로 표현할 수 없으므로 반례 처리가 필요

•

종이의 적힌 수 중 최댓값을 구해 놓고, 이를 활용하면 효율적인 탐색 수행이 가능 (코드 참고)

풀이 소스 코드

import sys
si = sys.stdin.readline
n, m = map(int, si().split())
paper = [list(map(int, si().split())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]
# 상하좌우 탐색에 사용할 방향 인덱스 배열
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# 종이에서 가장 큰 값
max_val = max(map(max, paper))
# 결과값을 저장할 변수
result = 0
# DFS 함수
def dfs(x, y, cnt, total):
global result
# 남은 탐색 지점을 모두 최댓값으로 해도 현재까지의 result보다 작으면 해당 탐색은 조기종료
if result >= total + max_val * (4 - cnt):
return
# 4개의 정사각형을 모두 사용했다면
if cnt == 4:
result = max(result, total) # result값 갱신
else: # 아직 4개의 정사각형을 다 사용못한 경우
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == False:
# ㅜ, ㅗ, ㅏ, ㅓ 모양을 만들기 위한 반례 처리
if cnt == 2:
visited[nx][ny] = True # nx, ny 좌표는 방문 처리만 하고
dfs(x, y, cnt + 1, total + paper[nx][ny]) # x, y에서 다시 탐색 수행
visited[nx][ny] = False
visited[nx][ny] = True
dfs(nx, ny, cnt + 1, total + paper[nx][ny])
visited[nx][ny] = False
# 종이 2차원 배열 모든 요소에서 DFS 수행
for i in range(n):
for j in range(m):
visited[i][j] = True
dfs(i, j, 1, paper[i][j])
visited[i][j] = False
print(result)
Python