(24.11.05) DFS 응용과 백트래킹

 

 

DFS알고리즘에 대해서 학습을 했지만,

어떠한 조건에 따라서는 백트래킹의 여부에 대해서 고찰을 할 필요가 있어

조금 이해하는데 어려웠지만 한번더 점검을 해보면서 DFS를 적용하는 문제를 풀고

백트래킹에 대해서 다시 정리해보려고 했다.

---

DFS (Depth-First Search, 깊이 우선 탐색)

• 한 노드에 대해서 끝까지 자식 노드를 탐색한 뒤에 다음 노드로 넘어가는 전체 탐색 알고리즘
  • 이러한 전체 탐색의 알고리즘은 어떤 목표를 찾아가는 조건이 있을 경우 모든 경우의 수를 찾는 방향
• 따라서, 완전 탐색을 통해 최적의 답을 찾는 로직에서도 유용하게 사용할 수 있음

DFS의 직접적인 활용

• DFS는 가중치가 존재하지 않는 그래프에서 사용
  • 이 뜻은 여러가지의 선택의 경우의 수를 선택하는 상황(가중치가 X)에서 완전탐색을 가능하게 해주고, 조건을 부여해줄 수 있음

문제 :

주어진 초기 피로도 k로 여러 개의 던전을 최대한 많이 탐험하려 합니다. 각 던전에는 "탐험에 필요한 최소 피로도"와 "탐험 시 소모되는 피로도"가 2차 배열 dungeons로 주어지며, 가능한 던전 순서를 고려해 탐험 가능한 최대 던전 수를 반환

import java.util.*;

class Solution {
    
    public int maxVisit =0;
    
    public int solution(int k, int[][] dungeons) {
        
        dfs(k, dungeons);
        
        return maxVisit;
    }
    
    public void dfs(int k, int[][] dungeons) {
        boolean[] visited = new boolean[dungeons.length];
        
        dfsCheck(k, dungeons, visited);
    }
    
    // 조건에 따라 모두 탐험
    public void dfsCheck(int k, int[][] dungeons, boolean[] visited) {
      // 최대 방문수 갱신
        int visitCount = 0;
        for(boolean visit : visited) {
            if(visit) visitCount++;
        }
        maxVisit = Math.max(maxVisit,visitCount);
        
        for(int i =0; i < dungeons.length; i++) {
      // 방문이 안되었을 때만
            if(!visited[i]) {
                // 체력 >= 필로도 일때만
                if(k>=dungeons[i][0]) {
                    k -= dungeons[i][1];
                    visited[i] = true;
                    dfsCheck(k, dungeons, visited);
                    
                    // 깊이 탐색 종료 후 백트래킹
                   k += dungeons[i][1];
                    visited[i] = false;
                }
            }
        }
    }      
    
}

• 재귀법을 사용하여 Stack 사용X
• visited는 대게 Set 자료구조를 활요하게 되지만, 모든 선택 가지수를 알고 있기 때문에 boolean 배열을 사용
  • dungeons 자체가 배열로 구성되어있기 때문에 0번 인덱스 dungeon이 존재해서 visited 인덱스와 대응이 가능
    • 단, 다른 상황에 따라서 n개의 선택지일 경우, n+1 길이의 배열을 만들어서 첫번째 경우가 1번 boolean 인덱스 방문여부로 맞출 수 있음
  • 굳이 Set구조의 contains메서드를 사용할 필요없이 바로 직접적으로 방문여부를 빠르게 확인이 가능

완전탐색을 위한 백트래킹

• 한 노드(던전)에 반복해서 순서대로 방문하면서 진행을 하기 때문에, 다음의 반복에서 다시 방문 필요
  • 예를 들어, 던전 A, B, C가 있을 때, 백트래킹을 통해 A → B → C, A → C → B, B → A → C 등 모든 경로를 탐험할 수 있는 순서까지 고려를 해야하는 완전 탐색 = 조합, 순열 이기 때문에
• 이전에 정리했던 DFS 재귀 방법에서는 굳이 백트래킹을 할 필요가 없는, 단순한 전체 노드를 탐색하는 알고리즘 이었기 때문
•  
  • 백트래킹을 굳이 해서 똑같은 노드를 또 방문할 필요가 없음
    • A → B → (B의 자식) → B를 탐색 완료한 후 A로 돌아감 → A → C → (C의 자식) → C 탐색 순서이기 때문에
  • 특정 방문 조건 이 있더라도, 백트래킹을 할 필요가 없음

...
    private static void dfsCheck(int node, Set<Integer> visited) {
        visited.add(node);

        for (int neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                dfsCheck(neighbor, visited);
            }
        }
    }
...

 

• 미로 찾기에서의 백트래킹 
  • 미로 검증에서 실패가되어 dfsCheck 재귀 메서드에서 return해올 경우, 백트래킹을 통해서 다시 되돌아가는 로직

...
// 상하좌우로 재귀적으로 탐색
    for (int i = 0; i < 4; i++) {
      int newX = startX + DX[i];
      int newY = startY + DY[i];

      dfsCheck(newX, newY, endX, endY, visited, path, allPath);
    }

    // 상하좌우(검증 에서 return이 있을경우) 백트래킹
    visited[startX][startY] = false;
    path.remove(path.size() - 1);
  }
...

---