1. 문제 설명
https://www.acmicpc.net/problem/14500
내 첫 골드 문제였다!! 그리고 인생의 쓴 맛을 경험했었다.
난 이게 왜 아직도 고작 골드5밖에 안 되는지 모르겠다.
너무 화나서 함수 이름도 foku라고 지었다...
'ㅗ' 모양 테트로미노를 만들기 위한 전용 함수였으니 완전히 틀린 함수명은 아니다.
2. 아이디어
N, M의 범위가 크지 않기 때문에 전탐색을 써도 무방하다.
모든 row, col을 기준으로 이동가능한 모든 경로를 탐색한 후, 최댓값을 저장해놓으면 된다.
이게 왜 dfs 문제인데? 라는 생각이 들 수 있지만 아래 그림을 보면 쉽게 이해가 될 것이다.
다만 1에서 2로 이동한 후에 다시 1로 돌아가는 불상사를 막기 위해서 임시로
visited[0][0]을 방문처리(1)해두고 2는 3이나 4로만 이동할 수 있도록 조치할 필요가 있다.
이걸 3번 반복하면 최댓값 정산을 한 번 해주고 재귀에서 다시 빠져나온다.
문제는 'ㅗ' 모양은 dfs만으로 어떻게 만들 방법이 없어서
dfs가 끝나면 따로 함수를 구현해서 값을 구해야 한다.
합쳐보려고 엄청 노력했었는데 결국 포기했었던 기억이 아직도 생생하게 떠오른다.
3. 코드
n, m = map(int, input().split())
paper = [list(map(int, input().split())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]
move = [(-1, 0), (0, 1), (1, 0), (0, -1)] # up right bottom left
result = 0
def dfs(row, col, deepth, total):
global result
if deepth == 4:
result = max(result, total)
return
for m_r, m_c in move:
tmp_r = row + m_r
tmp_c = col + m_c
if 0 <= tmp_r < n and 0 <= tmp_c < m and visited[tmp_r][tmp_c] == 0:
visited[tmp_r][tmp_c] = 1
dfs(tmp_r, tmp_c, deepth + 1, total + paper[tmp_r][tmp_c])
visited[tmp_r][tmp_c] = 0
def foku(row, col, total):
global result
min_branch = 10000
branch = 0
if row == 0 or row == n - 1 or col == 0 or col == m - 1:
min_branch = 0
branch += 1
for m_r, m_c in move:
tmp_r = row + m_r
tmp_c = col + m_c
if 0 <= tmp_r < n and 0 <= tmp_c < m:
min_branch = min(min_branch, paper[tmp_r][tmp_c])
total += paper[tmp_r][tmp_c]
branch += 1
if branch == 4:
result = max(result, total - min_branch)
def solution():
for row in range(n):
for col in range(m):
visited[row][col] = 1
dfs(row, col, 1, paper[row][col])
visited[row][col] = 0
foku(row, col, paper[row][col])
print(result)
solution()