2022 03 10

2022-03-10

DFS 복습

• 중복을 허용하지 않고, 포함하느냐 안하느냐를 검사하고 싶음
• 그럼 다음과 같이, 해당 친구를 포함하느냐, 안하느냐를 두개의 DFS 재귀로 풀어내면 됨

  if (friendSelected == friendsToSelect) {
      if (MIN <= totalWeight && totalWeight <= MAX)
      {
          answer++;
      }
  } else {
      DFS(startIndex+1, friendSelected+1, totalWeight + friends[startIndex]));
      DFS(startIndex+1, friendSelected, totalWeight);
  }
  

• 헷갈린 부분
  • 순열과 조합... 해당 문제는 포함 하느냐 안하느냐는 단순한 이분법인데, 순열/조합 경우의 수를 생각함
  • 순열: 순서 상관 있이 선택 => {1, 2, 3} != {2, 1, 3}
    • 이러다보니 for문을 돌면서 해당 데이터를 넣고, visited[] 를 true로 만들어줬다가 재귀 끝나면 false로 푸는 로직이 필요
  • 조합: 순서 상관 없이 선택 => {1, 2, 3} == {1, 2, 3}
    • 이건 순서 상관없이 그냥 고르기만 하면됨
    • 그러다보니 for문 다음 index 부터 돌도록 훈련

      if (friendSelected == friendsToSelect) {
          if (MIN <= totalWeight && totalWeight <= MAX) {
              answer++;
          }
      } else {
          for(int i=startIndex; i<friendNumber; i++) {
              DFS(i + 1, selected + 1, total + friends[i]);
          }
      }