문제
테트로미노 [백준 14500]
https://www.acmicpc.net/problem/14500
테트리미노 도형을 리스트에 넣었을 때 도형이 차지하는 칸의 수의 합의 최대값을 구하는 문제이다.
풀이
첫째로 이 문제를 봤을 때 무조건 완전 탐색으로 풀어야겠다라고 다짐했다. 회전할 때나 대칭일 때의 테트리미노의 모양만 잘 생각해서 수를 더하면 될 거 같기 때문이다. 결국 1시간 좀 넘는 시간 동안 함수 5개를 구현했고 vscode에서 예시 출력까지 제대로 나오는 것을 확인했다. 다행히 문제를 맞출 수 있었다. 하지만 이건 코테에서 만나면 무조건 안 풀고 넘어갈 문제일 게 뻔한 터라 다른 풀이를 생각해야 했다. 그러다 생각한 게 바로 깊이 탐색이다.
4개의 블록으로 만들수 있는 모양은 5개가 최대이기 때문에 다음 블록 위치를 바꿔가며 더해주면 되지 않을까? 라는 생각이 들었고 'ㅗ' 모양을 제외하고는 모두 구현할 수 있음을 확인했다. 'ㅜ' 모양은 ㅁㅁ 에서 ㅁㅁㅁ, 혹은 ㄱ자 모양으로 가기 전에 재귀함수에 x, y 값을 현재 위치로 파라미터 설정을 해주면 되는 것이었다.
코테에서는 시간도 부족하고 긴장할터라 이런 꼼꼼한 문제는 실수를 할 확률이 높아보였다. 때문에 실행에 옮기기 전에 다른 풀이를 생각해보자는 생각이 들었다.
코드
생으로 함수 구현
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
answer = []
def tetris1():
result = 0
for i in range(n):
for j in range(m):
temp = 0
if j == m - 1 or i == n - 1:
continue
temp += board[i][j] + board[i][j + 1] + board[i + 1][j] + board[i + 1][j + 1]
result = max(temp, result)
return result
def tetris2():
result = 0
for i in range(n):
for j in range(m):
temp = 0
if j >= m - 3:
continue
temp += sum([board[i][j + d] for d in range(4)])
result = max(temp, result)
for i in range(n):
for j in range(m):
temp = 0
if i >= n - 3:
continue
temp += sum([board[i + d][j] for d in range(4)])
result = max(temp, result)
return result
def tetris3():
result = 0
for i in range(n):
for j in range(m):
if i < 2 or j == m - 1:
continue
temp = board[i][j] + board[i - 2][j] + board[i - 1][j] + board[i][j + 1]
result = max(temp, result)
for i in range(n):
for j in range(m):
if i < 2 or j == 0:
continue
temp = board[i][j] + board[i - 2][j] + board[i - 1][j] + board[i][j - 1]
result = max(temp, result)
for i in range(n):
for j in range(m):
if i >= n - 2 or j == m - 1:
continue
temp = board[i][j] + board[i + 2][j] + board[i + 1][j] + board[i][j + 1]
result = max(temp, result)
for i in range(n):
for j in range(m):
if i >= n - 2 or j == 0:
continue
temp = board[i][j] + board[i + 2][j] + board[i + 1][j] + board[i][j - 1]
result = max(temp, result)
for i in range(n):
for j in range(m):
if j >= m - 2 or i == n - 1:
continue
temp = board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i + 1][j]
result = max(temp, result)
for i in range(n):
for j in range(m):
if j >= m - 2 or i == 0:
continue
temp = board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i - 1][j]
result = max(temp, result)
for i in range(n):
for j in range(m):
if j < 2 or i == n - 1:
continue
temp = board[i][j] + board[i][j - 1] + board[i][j - 2] + board[i + 1][j]
result = max(temp, result)
for i in range(n):
for j in range(m):
if j < 2 or i == 0:
continue
temp = board[i][j] + board[i][j - 1] + board[i][j - 2] + board[i - 1][j]
result = max(temp, result)
return result
def tetris4():
result = 0
for i in range(n):
for j in range(m):
if i == 0 or i == n - 1 or j == m - 1:
continue
temp = board[i][j] + board[i - 1][j] + board[i][j + 1] + board[i + 1][j + 1]
result = max(temp, result)
for i in range(n):
for j in range(m):
if i == n - 1 or j == m - 1 or j == 0:
continue
temp = board[i][j] + board[i + 1][j] + board[i][j + 1] + board[i + 1][j - 1]
result = max(temp, result)
for i in range(n):
for j in range(m):
if i == 0 or i == n - 1 or j == m - 1:
continue
temp = board[i][j] + board[i + 1][j] + board[i][j + 1] + board[i - 1][j + 1]
result = max(temp, result)
for i in range(n):
for j in range(m):
if i == n - 1 or j == m - 1 or j == 0:
continue
temp = board[i][j] + board[i + 1][j] + board[i + 1][j + 1] + board[i][j - 1]
result = max(temp, result)
return result
def tetris5():
result = 0
for i in range(n):
for j in range(m):
if j == m - 1 or j == 0 or i == n - 1:
continue
temp = board[i][j] + board[i][j - 1] + board[i][j + 1] + board[i + 1][j]
result = max(temp, result)
for i in range(n):
for j in range(m):
if j == m - 1 or j == 0 or i == 0:
continue
temp = board[i][j] + board[i][j - 1] + board[i][j + 1] + board[i - 1][j]
result = max(temp, result)
for i in range(n):
for j in range(m):
if i == n - 1 or i == 0 or j == m - 1:
continue
temp = board[i][j] + board[i - 1][j] + board[i + 1][j] + board[i][j + 1]
result = max(temp, result)
for i in range(n):
for j in range(m):
if i == n - 1 or i == 0 or j == 0:
continue
temp = board[i][j] + board[i - 1][j] + board[i + 1][j] + board[i][j - 1]
result = max(temp, result)
return result
answer.append(tetris1())
answer.append(tetris2())
answer.append(tetris3())
answer.append(tetris4())
answer.append(tetris5())
print(max(answer))
dfs
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1] #상하좌우
max_value = max(map(max, board)) #제일 큰 값
answer = 0
visited = [[False] * m for _ in range(n)] #들렸던 곳
def dfs(x, y, cnt, total):
global answer
if total + max_value * (4 - cnt) <= answer: # 남은 블록을 제일 큰수로 채워도 answer보다 크지 않을 때
return #탈출
if cnt == 4: # 블록 4개면 탈출
answer = max(answer, total)
return
for d in range(4): # 4방향 탐색
nx = x + dx[d]
ny = y + dy[d]
if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]: # 들리지 않은 곳일 때
if cnt == 2: #'ㅜ' 모양의 경우
visited[nx][ny] = True
dfs(x, y, cnt + 1, total + board[nx][ny]) #total에는 더해주지만 현 위치는 바꾸지 않음
visited[nx][ny] = False
# 재귀적 호출
visited[nx][ny] = True
dfs(nx, ny, cnt + 1, total + board[nx][ny])
visited[nx][ny] = False
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)
.