깊이 우선 탐색(DFS) - 타겟 넘버 / 네트워크

타겟 넘버 (DFS: 깊이 우선 탐색)

숫자 배열에서 각 숫자에 더하기(+)와 빼기(-)를 적용해 주어진 타겟 넘버를 만드는 방법의 수를 계산하는 문제

풀이 전략

1. DFS 함수 정의
   • dfs(index, currentSum) 형태로 정의.
   • index는 현재 탐색 중인 숫자의 인덱스를 나타낸다.
   • currentSum은 현재까지 계산된 합계를 나타낸다.
2. 기저 조건
   • index === numbers.length인 경우, 모든 숫자를 사용한 상태이다.
   • 이때 currentSum이 target과 같다면 경우의 수를 증가시킨다.

3. 재귀 호출

   • 현재 숫자를 더하는 경우와 빼는 경우를 각각 재귀적으로 호출한다.
   • dfs(index + 1, currentSum + numbers[index]): 숫자를 더함.
   • dfs(index + 1, currentSum - numbers[index]): 숫자를 뺌.

   • 트리 형태로 모든 경우의 수 탐색:

                         0
                     +1     -1
                 +1   -1  +1   -1
             +1  -1 +1 -1 +1 -1 +1 -1
           +1 ...
     

   • 각 경로에서 누적된 합이 target인 경우를 확인.
4. 초기 호출
   • dfs(0, 0)으로 초기화하여 탐색 시작. 처음에는 인덱스 0에서 합계가 0인 상태로 시작한다.

알고리즘 풀이

function solution(numbers, target) {

	let answer = 0;

	// 1. DFS 함수 정의
	function dfs(index, currentSum) {

		// 모든 숫자를 사용한 경우
		if(index === number.length) {

			if(currentSum === target {
				answer++; // 경우의 수 추가
			}

			return;
		}

		// 2. 재귀 호출
		// 현재 숫자를 더하는 경우
		dfs(index + 1, currentSum + number[index]);
		]

		// 현재 숫자를 빼는 경우
		dfs(index + 1, currentSum - numbers[index]);
	}

	// DFS 탐색 시작
	dfs(0, 0);

	return answer;

}

시간 복잡도

• DFS 탐색의 깊이는 numbers.length이며, 각 숫자에 대해 +와 `` 두 가지 경우를 탐색한다.
• 따라서 시간 복잡도는 O(2^n)이다.
• 주어진 제한 조건(최대 20개의 숫자)에 따라 최악의 경우 2^20 = 1,048,576번의 연산을 수행하게 된다.

---

네트워크

그래프 탐색(DFS 또는 BFS)을 활용하여 각 네트워크의 개수를 찾는 전형적인 문제

풀이 전략

1. 방문 체크
   • visited 배열을 사용하여 이미 확인한 컴퓨터를 기록한다.
2. DFS 탐색
   • 특정 컴퓨터에서 시작해 연결된 모든 컴퓨터를 방문 처리한다.
   • 인접 행렬 computers[node][i] 값이 1이면 연결되어 있음을 의미한다.
3. 네트워크 개수 증가
   • 방문하지 않은 컴퓨터에서 DFS를 시작하면, 이는 새로운 네트워크가 시작된다는 뜻이다.
   • DFS 탐색이 끝날 때마다 네트워크의 개수를 1 증가시킨다.
4. 최종 반환
   • 모든 컴퓨터를 탐색하며 발견한 네트워크의 개수를 반환한다.

알고리즘 풀이

function solution(n, computers) {
  let visited = new Array(n).fill(false); // 방문한 컴퓨터 기록
  let networkCount = 0;

  // DFS 탐색
  function dfs(node) {
    visited[node] = true; // 현재 컴퓨터 방문 처리

    for (let i = 0; i < n; i++) {
      // 연결되어 있고, 아직 방문하지 않은 컴푸터 탐색
      if (computers[node][i] === 1 && !visited[i]) {
        dfs(i);
      }
    }
  }

  // 모든 컴퓨터 탐색
  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      // 방문하지 않은 컴퓨터 발견 시 새로운 네트워크로 간주
      dfs(i);
      // DFS 탐색이 끝날 때마다 네트워크의 개수를 1 증가
      networkCount++;
    }
  }

  return networkCount; // 네트워크 개수 반환
}

시간 복잡도

1. DFS 탐색:
   • 모든 노드를 방문하며 연결된 노드를 탐색한다.
   • 최악의 경우 모든 컴퓨터가 연결되어 있어 탐색이 O(n^2)가 된다(인접 행렬의 크기).
2. 전체 복잡도:
   • O(n^2)

---