[파이썬]백준 14500 테트로미노

백준 14500 테트로 미노

---

문제 접근

이 문제를 처음 봤을 땐, 일반적인 DFS문제라고 생각했다. 완전탐색으로 탐색하고, 테트로미노는 정사각형 4개 임으로, 조건문 조건 걸고 진행하였지만 이 방식으론 문제를 풀수 없었다,,,

일반적인 DFS랑은 접근하면 테트로미노 모양중 'ㅗ' 모양을 탐색 할 수 없다..

그래서 'ㅗ'모양을 탐색하려면 L(인덱스)= 2일때 , 즉 두개의 블럭을 선택했을 떄 새로운 블럭에서 다음 블럭이 아닌 다시 기존 블럭에서 탐색하게 만들면 ㅗ 모양을 만들수 있다.

그 후 가지치기 하는 코드를 추가했다.

여태 백트래킹을 풀 때 최소값을 구하는 경우는 쉽게 가지치기를 했는데 최대값을 구하는 경우엔 가지치기를 해본적이 없어서 생각도 못했다.
종이(2차원배열)에서 최대값을 찾아서 max(map(max, arr))
선택할 수 있는 남은 블럭의 갯수만큼 (4 - L) 곱해주고
현재 누적합 total 에 더해서 ans와 비교해주는 방식으로 가지치기를 했다.

ans >= total + max_val * (4 - L):을 하면 불필요한 탐색을 막을수 있어 시간 복잡도를 줄일 수 있다!

이렇게 가지치기를 하고 중복되는 코드를 합쳐주니 시간을 180ms로 극적으로 줄일 수 있었다.

정답 코드

import sys;
input=sys.stdin.readline
def DFS( L, total, x, y):
    global maximum
    if maximum>=total+max_val*(4-L):
        return
    if L==4:
        maximum=max(total, maximum)
        return
    else:
        for i in range(4):
            xx=x+dx[i]
            yy=y+dy[i]
            if 0<=xx<n and 0<=yy<m and visit[xx][yy]==0:
                if L==2:
                    visit[xx][yy]=1
                    DFS(L+1, total+a[xx][yy],  x, y)
                    visit[xx][yy]=0
                visit[xx][yy]=1
                DFS(L+1, total+a[xx][yy],  xx, yy)
                visit[xx][yy]=0
                
n,m =map(int, input().split())
a=[list(map(int, input().split())) for _ in range(n)]
visit=[([0]*m) for _ in range(n)]
maximum=0
max_val=max(map(max , a))
dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
for i in range(n):
    for j in range(m):
        visit[i][j]=1
        DFS(1, a[i][j], i ,j)
        visit[i][j]=0
        
print(maximum)

⭐️중요 코드⭐️

if L==2:
	visit[xx][yy]=1
	DFS(L+1, total+a[xx][yy],  x, y)
	visit[xx][yy]=0

두번째 블럭에서 'ㅗ'모양을 탐색이 가능하다.

---

결론

• DFS문제라고 무작정 탐색하는 것이 아닌, 문제의 조건에 따라 변형해야 한다.
• 이 문제에서는 백트래킹 조건을 걸지 않으면, 시간 초과가 난다. 백트래킹 조건하나 시간 복잡도가 많이 달라지니 항상 효율성을 극대화 하는 방법을 생각하자!