14500: 테트로미노

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

14500번: 테트로미노

설명

맵 위에 테트로미노 하나를 놓아서 놓인 칸에 쓰여 있는 수들의 합을 최대로 구하는 문제이다. 테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야하며, 회전이나 대칭을 시켜도 된다. 

핵심 아이디어

• DFS를 활용하기!

테트로미노를 살펴보면 5개중 4개는 DFS로 구현이 가능한데 한 개는 불가능하다. T자를 구현하기 위해서는 DFS를 돌 때, 현재 위치를 가리키는 커서를 움직이지 않도록 해야한다.

출처: https://velog.io/@cjkangme

ㅜ 를 제외하고 나머지 테트로미노는 dfs로 상하좌우 최대 4번까지 돌려서 모양을 얻을 수 있지만 ㅜ는 특이 케이스로 따로 해주어야 한다.

회전과 대칭 시킨 모양들

이 모양들은 상 하 좌 우로 단 4번의 움직임으로 나올 수 있는 모양들이다. 이제 ㅜ 를 확인해 보자! 이 경우엔 가운데를 중심으로 3개의 사각형을 고려하면 된다. 즉 커서를 고정시킨다. 그래서 dfs로는 구현이 불가능하고 다음 4가지 경우를 순차적으로 확인하면 된다.

 

• dfs를 돌릴 때, 중복 방문을 피하기 위해 visited 2차원 배열을 만들어서 확인한다. dfs 탐색이 끝나면 다음 탐색을 위해서 방문 해제를 해준다. 

visited = [[False] * m for _ in range(n)]

• ㅜ 모양의 주변 블럭 부분을 확인할 때 방향 한 개만 뺀 경우를 고려할 때는 좌표를 미리 적어두어 사용해도 된다. 여기서는 4방향 모두 탐색한 후 그 4방향의 수 중에서 가장 작은 수를 제거하고 모두 더하기!

length = len(arr)
if length == 4:
	arr.sort(reverse=True) # 내림차순 정렬
    arr.pop() # 가장 오른쪽 데이터 추출 후 삭제
    max_value = max(max_value, sum(arr)+graph[x][y])
elif length == 3: # 3방향이면 바로 계산
	max_value = max(max_value, sum(arr)+graph[x][y])
return # 2이하면 ㅗ 모양을 만들 수 없기 때문에 return

코드 구현

import sys
input = sys.stdin.readline

# 맵의 크기 입력받기
n, m = map(int, input().split())
graph = []
for _ in range(n):
	graph.append(list(map(int, input().split())))
# 테트로미노를 놓았던 자리인지 확인하기 위한 배열
visited = [[False] * m for _ in range(n)]

# 상 하 좌 우
dx = [-1,1,0,0]
dy = [0,0,-1,1]

# 최댓값 변수
max_value = 0
# ㅗ,ㅜ,ㅓ,ㅏ를 제외한 모양들 dfs를 돌며 최댓값 구하기
def dfs(x,y, temp, count):
	global max_value
	# 모양이 완성되었을 때 최댓값 구하기
	if count == 4:
		max_value = max(max_value, temp)
		return
	else:
		# 상 하 좌 우로 이동
		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:
				visited[nx][ny] = True
				dfs(nx,ny,temp+graph[nx][ny],count+1)
				# 탐색 종료 후 다음 탐색을 위해 방문 해제
				visited[nx][ny] = False
# ㅜ,ㅗ,ㅓ,ㅏ 모양의 최댓값 계산
def excep(x,y):
	global max_value
	# 초기값은 시작점으로 설정
	temp = graph[x][y]
	# 4방향 탐색 값을 저장할 배열
	arr = []
	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:
			arr.append(graph[nx][ny])
	length = len(arr)
	if length == 4:
		arr.sort(reverse=True)
		arr.pop() # 가장 오른쪽 데이터 추출 후 삭제!
		max_value = max(max_value, sum(arr) + graph[x][y])
	elif length == 3: # 3 방향만 들어가기 때문에 바로 sum
		max_value = max(max_value, sum(arr) + graph[x][y])
	return # length가 2 이하라면 ㅗ 모양이 아니므로 바로 return

# 이제 정답 출력하기
for i in range(n):
	for j in range(m):
		# 현재 위치는 방문처리
		visited[i][j] = True
		# dfs 탐색하기
		dfs(i,j,graph[i][j], 1)
		excep(i,j)
		# 다음 탐색을 위해 방문처리 해제
		visited[i][j] = False
print(max_value)

참고 블로그

https://cijbest.tistory.com/87

[백준 14500 : PYTHON] 테트로미노

 

https://cobokjang.tistory.com/9

[백준] 14500번(python 파이썬) - 테트로미노