[알고리즘][JAVASCRIPT] DFS : 깊이 우선 탐색 + 프로그래머스 예제 <피로도>

DFS

Depth-First Search. 깊이 우선 탐색

그래프 탐색 알고리즘 중 한 가지이다.

(그래프 탐색 알고리즘에는 흔히 너비 우선 탐색(BFS)와 깊이 우선 탐색(DFS)가 있다.)

 

 

DFS는

그래프의 시작점에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 완벽히 탐색한다.

모두 완벽히 탐색한다는 것은 아래 깊숙히까지 꼼꼼히 전부 방문한다는 것.

 

재귀 혹은 스택을 통해 탐색을 수행하며

더 이상 아래로 갈 곳이 없을 때까지 탐색하면 위로 다시 올라가 다음 브랜치로 넘어간다.

 

 

 

[출처] https://jin1ib.tistory.com/entry/BFS-DFS-1

 

 

DFS의 특징

• 자기 자신을 호출하는 순환 알고리즘의 형태를 갖거나, 명시적인 스택을 사용한다.
  
  • 스택을 사용하는 경우, 방문한 정점들을 스택에 저장했다가 꺼내는 과정을 이용한다.
• 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.
  • 그렇지 않을 경우 무한 루프에 빠질 위험이 있다.

 

 

 

---

DFS 관련 JavaScript 코딩테스트 문제 풀이

[프로그래머스] 87946번. 피로도 

 

위 문제에서 만일 던전이 [[80, 20], [50, 40], [30, 10]] 3개 존재하는 경우

• [80, 20] -> [50, 40] -> [30, 10]
• [80, 20] -> [30, 10] -> [50, 40]
• [50, 40] -> [30, 10] -> [80, 20]

등 세 던전을 탐험하는 순서를 달리하면서 경우를 확인해야 한다.

=> 즉, 모든 가능한 경우의 수를 고려해야 하기에

=> => DFS를 이용해야겠다! 라고 생각하며 접근해야 하는 문제이다.

 

 

아래는 순환 함수 dfs() 를 이용해 풀이한 JavaScript 코드와 과정을 도식화한 그래프이다.

노란 숫자는 과정의 순서이며 위에서 보여준 그래프와 동일한 순서로 진행됨을 알 수 있다.

function solution(k, dungeons) {
    let answer = 0;
    
    // 탐험한 던전을 체크하기 위한 배열 초기화
    const check = Array(dungeons.length ).fill(false);

    // 2. 재귀함수를 이용해 완전탐색(DFS:깊이우선탐색) 진행
    function dfs(currentHp, depth){
        // console.log(`dfs(${currentHp}, ${depth}) 시작`);
        // 4. 현재 탐험한 던전 수를 최대값과 비교하여 최대 던전 수 업데이트
        answer = Math.max(answer, depth);
        
        // 3. 모든 던전을 탐험하는 경우를 검사
        for(let i=0; i<dungeons.length; i++){
            const [minHp, useHp] = dungeons[i];
            // 현재 피로도 확인 후 던전 탐색
            if(!check[i] && currentHp >= minHp) {
                check[i] = true; // 던전 탐험 표시
                // console.log(`check[i] 업데이트. check: ${check}, i: ${i}`)
                dfs(currentHp-useHp, depth+1); // 다음 던전으로 이동 : 탐험 횟수, 남은 피로도 업데이트
                // console.log(`dfs(${currentHp-useHp}, ${depth+1}) 탈출`)
                check[i] = false; // 던전 탐험 완료 표시 : 원복
            }
        }
    }

    dfs(k, 0); // 시작 피로도와 탐험 깊이 0으로 재귀함수 실행
    return answer;
}

 

 

 

---

참고

그래프 탐색 알고리즘(Graph Search Alogorithm)

[알고리즘] 깊이 우선 탐색(DFS)이란

[JS] BFS, DFS

프로그래머스 코딩테스트 연습 Level 2 - 피로도 (JavaScript)