DFS
기본적으로 DFS는 그래프 탐색 알고리즘이다.
DFS는 스택을 활용해서 문제를 풀어나간다. 그리고 DFS를 풀 때는 재귀함수를 활용하여 푸는 문제가 자주 나온다.
- 항상 종료조건을 먼저 생각하고
- 탐색 시작노드를 스택에 삽입한 후 방문처리 해주고
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리
- 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드 꺼내기
- 더이상 스택에 노드가 존재하지 않을 때까지 반복한다.
이진트리로 DFS알아보기
이진 트리를 탐색하는게 깊이우선탐색을 하는 것이 맞는데, 이제 어떤 일을 먼저 수행할 지를 선택하는 것이다.
자기 자신 노드의 값을 먼저 출력하고 넘어갈 지 등 코드 순서에 따라 정할 수 있다.
#깊이우선탐색 이진트리 순회
#전위 순회
def DFS(v):
if v > 7:
return #종료조건
else:
print(v, end = " ")
DFS(v*2)
DFS(v*2 + 1)
#중위 순회
def DFS2(v):
if v > 7:
return #종료 조건
else:
DFS(v*2)
print(v, end = " ")
DFS(v*2 +1)
#후위 순회
def DFS3(v):
if v > 7:
return #종료조건
else:
DFS(v*2)
DFS(v*2 + 1)
print(v, end = " ")⚽ 이걸 연습해본 이유는 이제 보통 DFS를 통해서 문제를 풀 때는 대부분 전위순회방식으로 문제를 풀꺼야 !!
자기 본연의 작업을 하고 넘어가는 방식으로 풀어나갈꺼야.
⚽ 문제를 풀 때 어떤 함수가 스택에 쌓이고 어디로 넘어가고, 그리고 함수가 끝나면 어디로 백트랙킹을 하고 등등 머릿속으로 시각화하면서 풀어나가자!!
문제풀 때 마인드
⚽ 부분집합 구하기(DFS)
자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요.
▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
▣ 출력설명
첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다.
단 공집합은 출력하지 않습니다.
▣ 입력예제 1
3
▣ 출력예제 1
1 2 3
1 2
1 3
1
2 3
2
3
import sys
from collections import deque
import heapq as hq
# sys.stdin = open("input.text", "rt")
N = int(input())
ch = [0] * (N+1) #1부터 시작하니까 편하게 0번 인덱스 버리고 생각.
def DFS(v):
if v > N: #종료조건
#종료조건때 해당 부분집합을 출력해줘야지
for i in range(1,N+1):
if ch[i] == 1:
print(i, end = " ")
print()
else:
ch[v] = 1 #체크한다는 것은 해당 원소를 부분집합에 포함한다는 뜻
DFS(v+1)
ch[v] = 0 #해당 원소 포함하는 모든 경우를 돌고온 후에 이제 포함하지 않는 경우도 생각
DFS(v+1)
DFS(1)-
해당 문제를 보면 부분집합을 구하는 문제이다. 처음에 DFS(v)를 만났을 때 v라는 원소를 현재 부분집합에 속하느냐, 속하지 않느냐로 2가지 나눌 수 있다. 또 해당 경우마다 다시 2가지의 경우로 나뉜다.
-
루트노드에서 뻗어나가는 형식을 상태 트리라고 하는데 DFS는 이러한 방식으로 풀어나가면 돼!
⚽ 이 문제에서는 해당 노드 값을 사용하느냐(부분집합 속하기) 사용하지 않느냐(속하지 않기)로 계속 뻗어나가는거야.
- 여기서 원소를 사용한다 안한다를 신호를 줘야 하는데 그걸 확인하는 check 리스트가 필요해 !
체크 한다는건(ch[v] = 1) 해당 원소를 부분집합에 포함시키겠다는 거고 이제 다음 노드를 호출해줘야지.
그리고 !! 아까 백트랙킹이 중요한 이유가 해당 경우를 포함시킨게 모두 끝나고 돌아오면 이제 해당 원소를 부분집합에 포합시키지 않는다는 경우도 추가해야지(ch[v] = 0) 이 경우도 다시 다음 노드를 호출해주면 돼 (DFS(v+1))
(아까 말한 이진트리에서의 탐색 과정을 이해해야 하는 이유가 여기 있었어)
- 이제 종료조건에서 해당 부분집합을 출력해주면 끝 !
🚗 DFS를 잘 하려면 이런 상태트리만 잘 구성하면 돼 ! 그 상태트리에 의해서 재귀만 잘 호출해주면 DFS문제를 쉽게 풀 수 있을거야.
- (DFS는 항상 종료조건을 잘 생각해야하는 것도 잊지말기 종료조건은 부분집합이 하나 완성되는 시점, 즉 N보다 커질 때겠지)
🚗 합이 같은 부분집합(DFS)
- 다른 문제를 통해 또 어떤 식으로 DFS를 접근하는 방식이 있는지 알아보자.
⚽ 합이 같은 부분집합(DFS : 아마존 인터뷰)
N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.
둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다.
예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.
▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.
▣ 출력설명
첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.
▣ 입력예제 1
6
1 3 5 6 7 10
▣ 출력예제 1
YES
import sys
N = int(input())
data = list(map(int, input().split()))
total = sum(data)
def DFS(L, sum):
if sum > total // 2:
return
if L == N: #종료조건. 끝까지 다 돌았잖아
if sum == (total - sum):
print("YES")
sys.exit(0) #그냥 끝내면 돼
else:
DFS(L+1, sum + data[L]) #현재 원소 추가하고 (L번 인덱스 추가) 다음으로 넘어감
DFS(L+1, sum) #현재 원소 추가하지 않고 다음 인덱스로 넘어감 !
DFS(0,0) #처음 인덱스부터 돌아야하고, 처음 합은 0이니깐
print("NO") #프로그램 종료 안되면 NO니까 출력해주면 됨.✈️ 해당 문제의 예시를 보면 6개 데이터가 주어졌을 때, 똑같이 문제를 보고 두 개의 부분집합 비교 하나의 숫자가 두 집합 중 어딘가에는 속해야 한다. 이 문제를 처음봤을 때 속한다, 속하지 않는다의 상태트리를 떠올리고 DFS로 접근할 줄 알았어야 했다.
2^6의 64가지의 경우가 나오는데, 먼저 내가 만든 부분 집합이 있겠는데 그걸 변수에 저장했다고 가정해보면 내 부분집합에 참여하지 않은 원소들은 또 다른 부분집합으로 생각할 수 있다 !
- 결국 이 문제는 내가 상태트리를 통해 만든 부분집합과 전체 총합에서 그 부분집합의 총합을 뺀 새로운 부분집합 총 2가지 부분집합을 비교하는 것이였다.
그 두합이 같다면 원하는 결과를 도출할 수 있어
🚀 문제 초반에 말했듯이 이 문제는 인덱스를 통해 접근하는 것을 생각하는거야 L은 리스트를 참조하는 인덱스 번호이고, sum은 내가 만든 부분집합을 누적하는 변수야.
⚽ 처음 인덱스부터 끝까지 다 확인해야 하기 때문에, 즉 해당 리스트를 전부 확인해야 하기 때문에, 인자로 인덱스를 주어서 처음부터 확인하는 경우로 풀 수도 있다.
L번 인덱스의 원소를 사용하겠다면 sum에 그 값을 더하면 되고 사용하지 않으면 그냥 더하지 않고 sum에 기존값을 주면 돼 이렇게 하면 해당 원소를 부분집합에 포합하겠다, 포함하지 않겠다를 의미한다. (L은 결국 상태트리의 레벨을 의미하기도 한다.)
🚀 하나 더 생각해야 하는게 DFS처럼 재귀를 활용하는 것은 시간절약이 필수이다 !
시간 절약할 수 있는 경우는 바로 탈출할 수 있게 예외처리를 해주는게 좋다.
-
이 경우에 있어서는 sum이 절반보다 커지면 탈출하면 된다. 이러면 시간 복잡도가 조금은 단축된다.
- 근데 이 경우 역시 커졌을 때 프로그램을 종료하면 안된다! 백트랙킹을 해서 다른 경우도 확인해야 하기에 return으로 끝내는 것이 맞다.
-
이런 식으로 해당 원소를 포함할지 말지를 결정할 수 있다 !!!!
-
계속 말하지만 DFS는 종료조건을 먼저 설정해야해
