백준 14500번: 테트로미노 (Python)

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

14500번: 테트로미노

접근

처음 문제를 보자마자 dfs 문제다! 하고 속으로 외쳤는데, 그렇게 간단한 dfs가 아님을 깨닫는데는 그리 오랜 시간이 걸리지 않았다. 일단 일반적인 dfs로는 ㅗ 모양을 체크할 수 없을 뿐더러, 당연하게도 굉장히 여러번 중복되는 계산을 해야하는데 해결 방법을 생각하는데 굉장히 많은 시간이 걸렸고, 결국은 풀지 못했다.

ㅗ 모양을 체크하는 것은 일반적인 dfs 에서 depth가 2일 때(즉, 2개의 블럭이 선택되었을 때), 세번째 칸을 선택하고 값을 합해 준 뒤 세번째 칸으로 이동하지 않고 두번째 칸에서 4번째 블럭을 추가로 탐색하여 합해주면 ㅗ 모양의 블럭 합을 구할 수 있게 된다.

중복 계산 없이 dfs 를 진행할 경우 블럭에 따라 같은 값이 두번에서 많게는 네번 계산하게 되는데, 이를 모두 걸러내는 방법을 찾기 위해 노력했지만 해결 하지 못했고, 다른 분들의 풀이를 참고하게 되었다. 결론은 모든 중복 계산을 걸러내는 풀이는 없는 것 같다. 하지만 탐색 과정에서 현재의 합 값에 종이에 주어진 최대값을 남은 depth 만큼 더해도 현재까지 계산된 max값을 초과할 수 없을 경우 계산을 종료하는 알고리즘을 추가하여 문제를 해결할 수 있었다.

코드

N, M = map(int, input().split())
B = []
max_val = 0
for i in range(N):
    B.append(list(map(int, input().split())))
    max_val = max(max_val, max(B[i]))
visited = [[0] * M for _ in range(N)]
ans = 0
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]


def dfs(r, c, depth, sum):
    global max_val, ans
    if ans >= sum + max_val * (4 - depth):
        return
    if depth == 4:
        ans = max(ans, sum)
        return
    for i in range(4):
        nr, nc = r + dr[i], c + dc[i]
        if 0 <= nr < N and 0 <= nc < M and visited[nr][nc] == 0:
            if depth == 2:
                visited[nr][nc] = 1
                dfs(r, c, depth + 1, sum + B[nr][nc])
                visited[nr][nc] = 0
            visited[nr][nc] = 1
            dfs(nr, nc, depth + 1, sum + B[nr][nc])
            visited[nr][nc] = 0


for i in range(N):
    for j in range(M):
        visited[i][j] = 1
        dfs(i, j, 1, B[i][j])
        visited[i][j] = 0

print(ans)

더 생각해 볼 것?

다른 분들의 풀이를 보니 오히려 dfs로 풀기 보다는 가능한 테르노미노 모양을 리스트업 해서 푸는 방법을 더 많이 쓰는 것 같았다. 더 직관적이고, 생각하기 쉽다고 느껴졌으나 경우의 수가 작기 때문에 가능한 방법이라고 생각되어 따로 풀어보지는 않았다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!