https://school.programmers.co.kr/learn/courses/30/lessons/43165
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
[알고리즘] 깊이 우선 탐색(DFS)
깊이 우선 탐색 ( Depth-First Search ) 루트 노드에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 특징 1. 모든 노드를 방문하고자 하는 경우에 사용한다. 2. 단순 검
mag1c.tistory.com
프로그래머스 기준 전반적인 2레벨 문제나, 적당한 3레벨문제 정도는 풀 수 있다고 판단되어
미뤄놨던 완전탐색 알고리즘을 연습하기 시작했다.
풀이
문제에서 모든 경우의 수를 파악하라고 했기 때문에 깊이 우선 탐색 알고리즘을 사용하여 해당 문제를 풀었다.
현재 어디까지 탐색했는지 필요했고, 탐색 위치에 따른 합계가 필요해서 각각 idx, sum 파라미터를 사용했다.
class Solution {
int answer = 0;
public int solution(int[] numbers, int target) {
dfs(numbers, target, 0, 0);
return answer;
}
public void dfs(int[] numbers, int target, int idx, int sum){
if(idx == numbers.length){
if(target == sum) answer++;
return;
}
dfs(numbers, target, idx+1, sum+numbers[idx]);
dfs(numbers, target, idx+1, sum-numbers[idx]);
}
}
예시 2번인 int[] numbers = {4,1,2,1}, target = 4인 상황을 예로 들면 아래와 같은 그림처럼 될 것이다.
가장 최후의 노드까지 탐색이 끝나면 리턴시켜 이전 노드로 돌아가며
모든 탐색이 끝나면 종료된다.
if(idx == numbers.length){
if(target == sum) answer++;
return;
}
BFS를 먼저 다뤄보다가 전혀 감이 안와서 DFS 문제를 풀어보았는데 어느정도 DFS는 다룰 수 있을 것 같다
