회고록/Java dataStructure&Algorithm

DFS (Def) feat 피로도 문제(프로그래머즈)

sehunbang 2024. 3. 19. 11:30

 

DFS 기본 이해

 

 

그래프 순회 방식의 일종. 거의 항상 너비우선탐색(BFS; Breadth First Search)과 비교되어 나온다.

 

 

트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식.

 

대표적으로 백트래킹에 사용한다.

일반적으로 재귀호출(Recursion!)을 사용하여 구현하지만,

단순한 스택 배열로 구현하기도 한다. 구조상 스택 오버플로우를 유의해야 한다.

 

 

장점

  • 단지 현 경로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적다.
  • 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

단점

  • 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제로는 미리 지정한 임의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수 있다.
  • 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

 

 DFS 트리

한 정점을 두 번 이상 방문하지 않는 연결그래프에서 DFS 트리라는 유향트리 구조가 만들어진다.
  • Tree edge란 DFS중 a정점을 방문한 후 b정점을 처음 방문할 때, a→b의 유향간선을 말한다.
  • Back edge란 DFS중 a정점을 방문한 후 이미 방문한 b 정점을 방문할 때, b가 a의 조상일 때 a→b의 유향간선을 말한다,
  • Forward edge란 DFS중 a정점을 방문한 후 이미 방문한 b 정점을 방문할 때, a가 b의 조상일 때 a→b의 유향간선을 말한다.
  • Cross edge란 DFS중 a정점을 방문한 후 이미 방문한 b 정점을 방문할 때, a→b의 유향간선이 Back edge나 Forward edge가 아닌 경우를 말한다.

DFS 트리를 사용하면 unrooted tree를 rooted tree로 만들 수 있다. 이 경우에는 Tree edge 이외의 간선이 존재하지 않게 된다.

 

Depth-First Search using stack

• Depth-first search starts from a chosen vertex and marks it as “visited”,it then visits just one of its neighbours (unlike breadth first search which visits all of them)

• The algorithm moves to that neighbour and visits another adjacent vertex (that hasn’t previously been visited).

• Process repeats until no possible vertex to visit, in which case the algorithm will backtrack until it finds a vertex which has at least one unvisited neighbour.

• Algorithm finished when each vertex has been visited.

 

 

• Question: What would be a suitable data structure to use storing vertices as the algorithm is visiting them?

• Answer: A Stack!

 

• Add initial vertex to stack and push on one of its unvisited adjacent neighbours, current vertex is the element on top of the stack. Should also keep suitable data structure of visited vertices.

 

• Repeat process with the element on top of the stack pushing on one of its unvisited adjacent neighbours. If the current vertex has no unvisited neighbours then pop off the stack until the top element has at least one unvisited neighbour to push on the stack.

• Algorithm terminates when the stack becomes empty

Depth first search can also easily be implemented using recursion! 

Use the program stack which pushes and pops off activation records every time a recursive method is called

static boolean[] visited = new boolean[7]; //방문 배열
static ArrayList<Integer>[] A = new ArrayList[7];//ArrayList타입 배열

public static void main(String[] args){

  //배열의 각 요소마다 ArrayList를 가진다.
  for(int i=1;i<=6;i++) {
    A[i] = new ArrayList<>();
  }
  ........
  //1번노드에서 DFS 실행
  DFS(1);
  System.out.println(procedure.toString());

 

Stack 이용

public static void DFS(int i){
  Stack<Integer> stack = new Stack<>();
  stack.push(i);;
  while(!stack.isEmpty()){
    int cur = stack.pop();
    visited[cur] = true;
    //해당 노드의 인접리스트를 검사하며, 
    //visited가 false인 경우에 stack.push
    for (int j : A[cur]) {
      if(!visited[j]){
        stack.push(j);
      }
    }
  }
}

Recursion 이용

static void DFS(int v){
  //방문배열이 true면 return
  if(visited[v]) return;
  //v 노드에 방문했으므로, 해당 방문배열을 true 로 변경
  visited[v] = true;
  //해당노드의 ArrayList(인접노드)를 모두 돌며 방문배열이 false인 경우에
  for(int i : A[v]){
    if(!visited[i]){
      DFS(i); //해당 노드에 대해서 DFS를 다시 실행한다.
    }
  }
}

 

피로도 예제

Description

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한사항
  • k는 1 이상 5,000 이하인 자연수입니다.
  • dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
    • dungeons의 가로(열) 길이는 2 입니다.
    • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
    • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
    • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
    • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.
입출력 예
 

90     ,     [[80,20],[50,40],[30,10]]

정답은 3

입출력 예 설명

현재 피로도는 80입니다.

만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면

  • 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
  • 남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.
  • 남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.

만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면

  • 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
  • 남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
  • 남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.

따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.

class Solution {
  static boolean[] visited;
  static int answer = 0;
  public static int solution(int k, int[][] dungeons) {
    ///bfs ? dfs?
    visited = new boolean[dungeons.length];
    int counter = dfs(dungeons,k,visited,0);
    return counter;
  }
  public static int dfs(int[][] dungeons, int k, boolean[] history, int count){
    for (int i = 0; i < dungeons.length; i++) {
      if(!history[i] && k >= dungeons[i][0]){
        history[i] = true;
        dfs(dungeons,k - dungeons[i][1], history, count + 1);
        history[i] = false;
      }
    }
    answer =  Math.max(answer, count);
    return answer;
  }
  public static void main(String[] args) {
    int k = 80;
    int [][]d ={{80,20},{50,40},{30,10}};
    System.out.println(solution(k,d));
  }
}