dfs

문제 설명 문제 풀이 방법 나는 이 문제를 보고 dfs로 풀자는 생각을 못하고 순열을 이용해 풀려했다..... dfs로 풀어야지 완전탐색이 가능하다고 생각했지만 dfs 구현을 잘 못해서 결국 힌트를 봤다.... dfs는 각 노드별 방문여부를 체크할 수 있는 배열을 만들고 재귀를 이용해 문제를 풀어간다. 내가 낮설었던 것은 재귀한 뒤 방문여부 배열을 다시 초기화 하는 것이였다. 코드 const solution = (k, dungeons) => { // dfs로 문제를 풀면 방문하는 노드가 방문을 했었는지 기록하는 것이 중요하다. (무한 루프에 빠질 수 있음) let answer = 0; let visited = Array(dungeons.length).fill(false); const dfs = (poin..

문제 설명 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요. 제한 사항 nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다. nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다. 문제 풀이 방법 이 문제는 우선 소수 판별 함수를 한개 미리 선언하고 그 다음에 문제를 풀었다. DFS를 적용해 문제를 풀었다. 소수임이 판별되면 answer에 1을 더하도록 해서 문제를 해결했다. 내가 작성한 코드 const isPrime = ..

문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한 사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers..

문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한 사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 1000 이하인 자연수입니다. 문제 풀이 방법 DFS를 처리할 함수를 생성한다. 함수는 노드를 방문 여부를 기록하는 count와 numbe..

깊이 우선 탐색 (DFS, Depth-First-Search) 정의 루트 노드 (혹은 임의의 다른 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 넓게 탐색하기 전에 깊게 탐색하는 것이다. 특징 1) 깊이 우선이 너비 우선(BFS)보다 간단하지만 느리다. 2) 자기 자신을 호출하는 순환 알고리즘의 형태를 갖는다. 3) 전위 순회(Pre-Order Traversals) 를 포함한 다른 형태의 순회는 모두 DFS의 한 종류이다. 주의점 그래프 탐색의 경우 어떤 노드를 방문했는지 검사해야 무한루프에 빠질 위험이 없다. 동작원리 a노드(시작노드) 방문 - 방문을 표시한다 a와 인접한 노드들을 차례로 순회 - 인접한 노드가 없다면 종료 a와 이웃된 노드b를 방문했다..