DFS - 타겟넘버.

• DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다
• DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있다면, 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
  

 

 

 

 

 

 

 

 

 

 

DFS 문제 예시

• 프로그래머스 - 타겟넘버
  • 재귀로 모든 경우의 수(+,-)로 다 넣어서 구현
  • 만들어진 최종의 값이 target과 동일한 경우 answer++

  class Solution {
        int answer = 0;
        public int solution(int[] numbers, int target) {
              dfs(numbers, target, 0);
              return answer;
        }
  
        public void dfs(int[] numbers, int target, int node) {
              if (node == numbers.length) {
                    int sum = 0;
                    for (int number : numbers) {
                          sum += number;
                    }
                    if (sum == target) {
                          answer++;
                    }
              } else {
                    numbers[node] *= 1;
                    dfs(numbers, target, node + 1);
                    numbers[node] *= -1;
                    dfs(numbers, target, node + 1);
              }
        }
  
  
  }

Uploaded by Notion2Tistory v1.1.0

-