DFS

[프로그래머스 / JS] 타겟 넘버 - Level 2

2023.04.13

🚩 문제 주소 📄 접근 방법 그래프 탐색 - DFS 더보기 DFS 함수 탈출 조건 depth가 주어진 numbers배열의 길이와 같아지면 재귀를 종료합니다. 그런데 종료하기전에 조건을 하나 판단합니다. 지금까지 구한 숫자의 합이 주어진 target과 같다면 answer를 1 늘려줍니다. 종료 조건에 만족하지 않는다면 dfs 함수를 2번 씩 재귀 호출합니다. depth를 1 늘려주고, 합에 숫자를 더하거나 뺍니다. 👨‍💻 나의 코드 function solution(numbers, target) { let answer = 0; const dfs = (depth, sum) => { if (depth === numbers.length) { if (sum === target) answer++; return; } ..

Algorithm

DFS를 가볍게 알아보자

2023.04.11

🥯 DFS 란? DFS는 Depth First Search의 약자로, 깊이 우선 탐색이라는 뜻을 가진 그래프 탐색 기법입니다. DFS는 시작 노드부터 탐색을 시작하면 가던 방향으로 탐색할 노드가 없을 때까지 쭉 탐색합니다. 탐색할 노드가 없다면 나눠져 있던 갈래까지 다시 올라와서 다음 분기를 똑같이 탐색합니다. 예를 들어, 미로의 탈출구를 찾는다고 했을 때, 한 길로 이동하다가 양 갈래 길을 만났습니다. 그 때, 일단 오른쪽 길로 쭉 이동합니다. 그런데 그 길은 막혀있는 길 이었습니다. 그래서 다시 아까 그 양 갈래 길로 이동해서 왼쪽 길로 이동합니다. DFS는 이런 느낌이라고 할 수 있습니다. 특징 노드를 방문하고 방문 체크를 해주어야 합니다. 하지 않으면 무한 루프에 빠질 수 있습니다. 단순 탐색 시..

[프로그래머스 / JS] 타겟 넘버 - Level 2

DFS를 가볍게 알아보자

티스토리툴바