[코딩테스트 - Java] DFS(깊이 우선 탐색) 문제

LeetCode가 자료구조 및 알고리즘 공부에 좋아보여서 병행하기로 했다.
오늘은 DFS에 대한 문제를 풀어보았다.

DFS란

DFS(깊이 우선 탐색)는 그래프나 트리 구조에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 모든 조건을 탐색할 때 사용하며, BFS(넓이 우선 탐색)와 같이 모든 노드를 지나며 방문한 노드를 체크하는 방식으로 진행한다.

DFS는 트리로 예를 들면 리프 노드까지 순회하고 다음 리프 노드를 찾기 때문에 깊이 우선 탐색이라고 한다.

재귀함수를 사용하거나 스택을 사용하여 탐색한다.

22. Generate Parentheses (릿코드)

주어진 n만큼의 괄호를 생성할 수 있는 경우의 수를 찾는 문제이다. 열려있는 괄호만큼 닫는 괄호가 있어야 한다.

• Input: n = 3
• Output: ["((()))","(()())","(())()","()(())","()()()"]

풀이 과정

재귀함수를 이용한 DFS 알고리즘으로 해결했고, 해결 전략은 이러하다.

1. 열려있는 괄호의 개수와 닫혀있는 괄호의 개수가 n이면 list에 추가

2. 열려있는 괄호의 개수가 n보다 작으면 str에 "("를 추가
   (StringBuffer를 사용중이므로 백트래킹 필요)

3. 같은 상태에서 open이 close보다 많으면 str에 ")"를 추가

4. 2,3 반복

import java.util.*;

class Solution {
    List<String> res = new ArrayList<String>();

    public List<String> generateParenthesis(int n) {
        generateStr(0,0, new StringBuffer(), n, res);

        return res;
    }

    public void generateStr(int open, int close, StringBuffer str, int n, List<String> list){
        int len = str.length(); // 백트래킹을 위한 길이 저장

        if(open == close && open + close == n * 2){
            list.add(str.toString());
            return;
        }
        if(open < n){
            generateStr(open+1, close, str.append("("), n, list);
            str.setLength(len);
        }
        if(close < open){
            generateStr(open, close+1, str.append(")"), n, list);
            str.setLength(len);
        }
    }
}

타겟넘버 (프로그래머스)

문제 내용

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

순서가 정해져있기 때문에 해당 배열의 index를 depth로 생각하고 풀이했다. 해결 전략은 다음과 같다.

1. depth가 배열의 길이와 같다면(인덱스를 넘어가면) 탐색 종료
2. 종료 시에 sum이 target과 같으면 count 증가
3. depth를 증가시키며 sum에 number를 더한 값으로 재귀
4. depth를 증가시키며 sum에 number를 뺀 값으로 재귀
5. 3,4번 반복

class Solution {
    int count = 0;
    
    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0, 0);
        return count;
    }
    public void dfs(int[] numbers, int target, int sum, int depth){
        if(depth == numbers.length){
            if(target == sum) count++;
            return;
        }
        dfs(numbers, target, sum+numbers[depth], depth+1);
        dfs(numbers, target, sum-numbers[depth], depth+1);
    }
}