DFS에서 max_value를 이용한 가지치기

🔍 요약: DFS에서 max_value를 이용한 가지치기란?

지금까지 더한 값 + 앞으로 더해질 수 있는 최대값이 현재의 최대 결과값(max_value)보다 작으면

더 이상 탐색해도 의미가 없으므로 중단한다.

 

📌 언제 쓰이는가?

테트로미노 문제처럼

• DFS로 블록 4개를 이어붙여 합을 계산하고,
• 최대값을 찾아야 하는 문제에서 사용됨.

 

💡 가지치기 핵심 로직

if current_sum + remain_max * (4 - depth) <= max_value:
    return

• current_sum: 지금까지 누적한 값
• remain_max: 아직 탐색하지 않은 칸 중 가장 큰 숫자
• 4 - depth: 앞으로 몇 개 더 선택해야 하는지
• max_value: 지금까지 구한 최고값

즉, 최선의 경우를 가정해도 max_value를 넘을 수 없다면 더 탐색하지 않음.

 

✅ 예시 코드 조각

def dfs(x, y, depth, total):
    global max_value

    # 가지치기: 최적의 경우에도 max_value를 넘을 수 없으면 중단
    if total + max_cell * (4 - depth) <= max_value:
        return

    if depth == 4:
        max_value = max(max_value, total)
        return

    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
            visited[nx][ny] = True
            dfs(nx, ny, depth + 1, total + board[nx][ny])
            visited[nx][ny] = False

 

• 여기서 max_cell은 전체 보드에서 가장 큰 값으로, 미리 계산해둔다.

max_cell = max(map(max, board))

 

🎯 효과

• 시간 복잡도 대폭 절감
• 불필요한 백트래킹 방지
• 탐색 깊이 4개 제한이 있어도 브루트포스로는 어려운 케이스 해결 가능

 

✅ 정리

항목	내용
이름	DFS 가지치기 (Pruning)
조건	현재값 + 앞으로 가능한 최대값 <= max_value
효과	시간 단축, 불필요한 탐색 제거
사용 예	테트로미노, 경로 최대합, 백트래킹 최적화