[231206] 프로그래머스 피로도 (Java)

• 깊이 우선 탐색(DFS, Depth-First Search)
  • 트리나 그래프를 탐색하는 기법 중 하나
  • 시작 노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘
  • 완전탐색 알고리즘
  • 주로 반복문을 활용하거나 재귀문을 통해 구현됨
• DFS의 기본 탐색 과정
  1. 현재 노드를 방문한 것으로 표시
  2. 방문한 표시가 되어 있지 않은 인접한 정점을 탐색
  3. 더 이상 방문하지 않은 정점이 없으면 이전 정점으로 역추적(backtracking)한다.
  4. 모든 정점을 방문할 때까지 프로세스를 반복
• DFS의 장단점
  • 장점
    • 목표가 특정 정점에 최대한 빨리 도달하는 것일 때 유용
  • 단점
    • 순환 그래프일 경우 무한 루프에 빠질 수 있음

---

피로도 문제가 완전탐색 문제인 것을 보고 DFS 알고리즘으로 해결하고 싶었다.
DFS 알고리즘을 구현해서 문제를 풀어본 경험은 있는데 오래되어서 거의 기억나지 않았기 때문이다.
문제를 풀면서 DFS에 조금 익숙해고자 했다.
문제를 풀긴 했으나 DFS를 잘 구현하지는 못했다는 생각이 들어서 정리하면서 풀이를 개선하려고 한다.

 

• 피로도

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

• 제출 코드

class Solution {
    static int[] flag = new int[8];
    static int now;
    static int max=0;
    static int num=0;
    
    public int solution(int k, int[][] dungeons) {
        int[] flag = new int[dungeons.length];
        now = k;
        for(int i=0; i< dungeons.length; i++)
            dfs(i, dungeons);
        return max;
    }
    
    public static void dfs(int d, int[][] dungeons){
        if(now >= dungeons[d][0]) now -= dungeons[d][1];
        else return;
        num++;
        if(num > max) max = num;
        flag[d] = 1;
        for(int i=0; i< dungeons.length; i++){
            if(flag[i]==0) dfs(i, dungeons);
        }

        flag[d] = 0;
        now += dungeons[d][1];
        num--;
    }
}

 

• solution의 for문과 dfs 내의 for문이 반복되고 있으므로 dfs안에 for문 하나만 남겨두는 방식으로 수정하면 좋을 것 같다.

class Solution {
    static boolean[] flag;
    static int max = 0;


    public int solution(int k, int[][] dungeons) {
        flag = new boolean[dungeons.length];
        dfs(k, dungeons, 1);

        return max;
    }

    public static void dfs(int tired, int[][] dungeons, int cnt) {

        for (int i = 0; i < dungeons.length; i++) {
            if (!flag[i] && tired >= dungeons[i][0]) {
                flag[i] = true;
                dfs(tired - dungeons[i][1], dungeons, cnt+1);
                flag[i] = false;
                if(max < cnt) max = cnt;
            }
        }
    }
}

• 기존에는 피로도(체력)을 flag처럼 더해줬다가 빼주고, 탐험한 던전 개수들도 전역변수를 선언하여 일일이 더해주고 빼주는 식으로 코드를 작성하였다.
  • 하지만 던전 개수와 피로도를 매개변수로 변형하지 않고 넘겨줌으로써 코드를 간결하게 만들 수 있었다.
• 추가적으로 flag의 길이도 던전의 길이와 같도록 생성하였다.
• 기존에 int형이었던 flag를 boolean 타입으로 변경하였다.

DFS 알고리즘으로 문제를 푸니까 코드가 간결해지면서 쉽게 풀 수 있어서 좋았다.
한 번 연습했으니 백트래킹으로 풀어야 하는 문제가 있으면 다시 적용해보도록 노력해야겠다.