문제 링크
문제 설명
폴리오미노란 1*1크기의 정사각형이 여러개 붙어있는 도형을 의미한다. 테트로미노는 정사각형 4개로 이루어진 폴리오미노를 의미하고, 이런 테트로미노에는 
다섯 종류가 있다. 각 칸에 1000미만의 자연수가 적힌 N*M크기의 종이에 하나의 티트로미노를 놓으려고 하는데 한 정사각형이 한 칸만 포함해야 하고, 회전과 대칭이 가능하다. 테트로미노가 놓인 칸 수의 합의 최대는 ?
문제 풀이
처음에 90도 180도 270도 회전, x축 y축 대칭 등 한 칸을 축으로 회전/대칭해보려다가 실패했다,, ^^
시도 1
특정 칸에서부터 dfs를 이용하여 가능한 모든 테트로미노블록의 리스트를 possibles에 넣고, possibles 리스트를 돌면서 최대값을 찾으려고 했다. 시간초과가 났는데, 굳이 possibles 리스트에 저장해서 최대값을 찾지 않고, dfs를 돌면서 가능한 테트로미노를 찾았을때 최대값을 갱신하면 시간을 줄일 수 있을 것 같다.
시도 2 - dfs
- dfs, bfs를 이용해서 (x,y)칸부터 이어진 4칸을 갖는 테트로미노를 찾는다.
#(x,y)를 시작으로 4칸 찾기
def dfs(x, y, block, count, max_num):
global answer
if count == 4:
answer = max(answer, max_num)
return
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if in_range(nx, ny) and (nx, ny) not in block:
dfs(nx, ny, block+[(nx, ny)], count+1, max_num+board[nx][ny])-> dfs, bfs를 이용하면 다섯개의 테트로미노 종류중 'ㅗ' 모양을 갖는 테트로미노는 찾을 수 없다. - 'ㅗ' 모양을 갖는 테트로미노 경우도 고려하기 위해서, 특정 칸의 동서남북 네방향을 확인한다.
-> 범위 내에 ㅗ모양이 가능하면, ㅗ를 이루는 칸들의 합을 구해서 max를 갱신
-> 범위 내에 + 모양이 가능하면, +를 이루는 칸들의 합에서 각 동서남북 칸중 최소값을 빼준다.
def exception(x, y):
global answer
tmp = []
min_val = 1000
for i in range(4):
if in_range(x+dx[i], y+dy[i]):
min_val = min(min_val, board[x+dx[i]][y+dy[i]])
tmp.append((x+dx[i], y+dy[i]))
# 범위 내에 ㅗ모양이 가능하면
if len(tmp) == 3:
tmp.append((x,y))
answer = max(answer, get_score(tmp))
#범위 내에 +모양이 가능하면 -> 네방향중 제일 작은 칸 빼서 ㅗ로 만들기
elif len(tmp) == 4:
tmp.append((x,y))
answer = max(answer, get_score(tmp)-min_val)전체 코드
import sys
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
answer = 0
N, M = map(int, input().split())
board = []
for _ in range(N):
board.append(list(map(int, input().split())))
def in_range(x, y):
if x in range(N) and y in range(M):
return True
return False
def get_score(blocks):
total = 0
for block in blocks:
total += board[block[0]][block[1]]
return total
#(x,y)를 시작으로 4칸 찾기 -> ㅗ모양은 포함 못함 ㅠ
def dfs(x, y, block, count, max_num):
global answer
if count == 4:
answer = max(answer, max_num)
return
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if in_range(nx, ny) and (nx, ny) not in block:
dfs(nx, ny, block+[(nx, ny)], count+1, max_num+board[nx][ny])
def exception(x, y):
global answer
tmp = []
min_val = 1000
for i in range(4):
if in_range(x+dx[i], y+dy[i]):
min_val = min(min_val, board[x+dx[i]][y+dy[i]])
tmp.append((x+dx[i], y+dy[i]))
# 범위 내에 ㅗ모양이 가능하면
if len(tmp) == 3:
tmp.append((x,y))
answer = max(answer, get_score(tmp))
#범위 내에 +모양이 가능하면 -> 네방향중 제일 작은 칸 빼서 ㅗ로 만들기
elif len(tmp) == 4:
tmp.append((x,y))
answer = max(answer, get_score(tmp)-min_val)
for i in range(N):
for j in range(M):
dfs(i, j, [(i,j)], 1, board[i][j])
#+모양도 추가하기
exception(i, j)
print(answer)시도 3 - bfs
bfs로도 풀어보았다,, 역시 dfs가 좀 더 직관적이고 짜기 쉬운듯,,,
import sys
from collections import deque
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
answer = 0
N, M = map(int, input().split())
board = []
for _ in range(N):
board.append(list(map(int, input().split())))
def in_range(x, y):
if x in range(N) and y in range(M):
return True
return False
def bfs(x,y):
max_num = 0
queue = deque()
#x, y, 이전 x, 이전 y, count, total_score
queue.append((x, y, 0, 0, 1, board[x][y]))
while queue:
x, y, pre_x, pre_y, cnt, total_score = queue.popleft()
if cnt == 4:
max_num = max(max_num, total_score)
continue
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
#이동한 좌표가 행렬의 범위를 만족하고, 해당 이동이 이전 좌표로의 이동이 아니면 !!
if in_range(nx, ny) and (nx, ny) != (pre_x, pre_y):
queue.append((nx, ny, x, y, cnt+1, total_score+board[nx][ny]))
return max_num
def get_score(blocks):
total = 0
for block in blocks:
total += board[block[0]][block[1]]
return total
def exception(x, y):
global answer
tmp = []
min_val = 1000
for i in range(4):
if in_range(x+dx[i], y+dy[i]):
min_val = min(min_val, board[x+dx[i]][y+dy[i]])
tmp.append((x+dx[i], y+dy[i]))
# 범위 내에 ㅗ모양이 가능하면
if len(tmp) == 3:
tmp.append((x,y))
answer = max(answer, get_score(tmp))
#범위 내에 +모양이 가능하면 -> 네방향중 제일 작은 칸 빼서 ㅗ로 만들기
elif len(tmp) == 4:
tmp.append((x,y))
answer = max(answer, get_score(tmp)-min_val)
for i in range(N):
for j in range(M):
answer = max(answer, bfs(i,j))
#+모양도 추가하기
exception(i, j)
print(answer)느낀점
테트로미노를 직접 회전시키려다가 한 세시간 날린듯 ,,^ㅇ^,, 풀이 찾아보니까 가능한 모든 테트로미노 좌표를 하드코딩해서 찾은 코드가 많았는데 출제자의 의도가 그게 아닌 것 같아서 다른 방법을 한참 고민했다,, dfs로는 ㅗ모양을 찾을 수 없어서 따로 고려해야 한다는 점에서 어려운 문제였던 것 같다.
정말루 쉽지 않았고,,
Hongik CE