🧚‍♂️알고리즘🧚‍♂️ - 완전탐색 - 깊이 우선 탐색(DFS)

깊이 우선 탐색(DFS)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색(최대 깊이까지)하는 방법

- 재귀 함수 이용

- 스택 자료구조 이용 ->후입선출 특성 필요

-노드 방문 여부를 체크할 리스트 필요

 

인접 리스트로 그래프 표현 ->방문리스트 초기화->시작노드 스택에 삽입->대상 노드의 인접 노드 스택 삽입->스택에 값이 없을 때까지 반복

단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등에 이용

---

🥈실버 2

11724

연결요소의 개수 구하기

11724번: 연결 요소의 개수

방행이 없는 그래프 -> 양쪽 에지를 모두 저장

모든 노드를 탐색하는 데 실행한 DFS개수가 곧 연결 요소 개수

# DFS
from sys import stdin
N, M  = map(int,stdin.readline().split())
nearList = [[] for _ in range(N+1)]# 인접 노드 저장 리스트
visited = [False]*(N+1) # 모든 노드 방문했는지 확인

# DFS
def DFS(v):
   visited[v] = True #v번쨰 노드 방문함
   for i in nearList[v] : #인접 노드들 전부 방문시킴
        if not visited[i]:
            DFS(i)# 재귀

# 인접 노드 저장하기
for _ in range(M):
    s,e  = map(int,stdin.readline().split())
    nearList[s].append(e)
    nearList[e].append(s)

count = 0 #덩어리 개수 (DFS 실행 횟수)

# 메인
for i in range(1,N+1):
    if not visited[i]:
        count+= 1
        DFS(i)

print(count)

-파이썬으로 하면 런타임에러 / 파이파이로 하기

---

🥇골드5

2023

신기한 소수 찾기

 

2023번: 신기한 소수

 

- 가지치기 방식 사용하기

첫째 자릿수 는 그 자체로도 소수가 되어야 함 = 2,3,5,7 중 선택

그 다음 자릿수부터는 일의 자릿수에 한번씩 오게 되므로 짝수 불가 = 1,3,5,7,9 중 선택

N자리까지 이 노드들을 재귀 함수 현태로 탐색함

from sys import stdin
N = int (stdin.readline())

# 소수 찾는 함수
def findthe(N):
    for i in range(2,N):
        if N % i == 0:
            return False
    return True

#DFS
def DFS(num):
    if len(num) == N:
        print(num)
        return
    else:
        for i in range(1,10,2):
            if findthe(num * 10 + i):
                DFS(num * 10 + i)

DFS(2)
DFS(3)
DFS(5)
DFS(7)

'int' has no len() 에러 유의..

파이썬 시간초과/ 파이파이로 하면 됨

 

...

소수 찾는 함수 반복문 int((N/2) +1)  까지만 돌리면 파이썬 시간초과 안남

숫자 반띵보다 큰 수로는 나눠질 수가 없다고.. 바보

---

🥇골드5 

13023

친구 관계 파악하기

 

13023번: ABCDE

 

- 깊이가 5인 ( DFS 재귀가 5번 이상 진행된) 사례가 있는지 확인하면 됨

 

모든 사람들에게서 시작해보기

 

각 사례에서 재귀함수가 몇 번 돌아갔는가?

=> 이걸 재귀함수상에서 정확히 보려면 변수로 따로 관리하면 안 되고 (여러 가지 뒤섞여서 돌아가므로) 함수의 인자로 관리하기!

 

한 가지에서 방문한 노드 다시 가지 않기

=> 14 /24줄 확인

 #이 가지의 뒷부분에선 현재 학생을 다시 방문하면 ㄴ 

#현재 cha로부터 뻗어나간 가지는 탐색이 끝났으므로 다른 가지에서 cha를 볼 수 있도록 해야 함

from sys import stdin
N, M = map(int, stdin.readline().split()) # 사람 수 / 관계 수 
Mlist = [[] for _ in range(N)] #학생 관계 리스트
isvisit = [1]*(N) # 방문햇으면 0
result = False

for _ in range(M): # 방향 양쪽으로 오케이 노드
    A , B = map(int, stdin.readline().split())
    Mlist[A].append(B)
    Mlist[B].append(A)

def DFS(cha, depth):
    global result # 변수 글로벌!
    isvisit[cha] = 0 #이 가지의 뒷부분에선 현재 학생을 다시 방문하면 ㄴ 
    
    if depth == 4:
        result = True
        return
    
    for j in Mlist[cha]:
        if isvisit[j]:
            DFS(j, depth + 1)
    
    isvisit[cha] = 1#현재 cha로부터 뻗어나간 가지는 탐색이 끝났으므로 다른 가지에서 cha를 볼 수 있도록 해야 함
    
# main
for cha in range(N):
    depth = 0
    DFS(cha,depth)

if result:
    print(1)
else:
    print(0)

변수는 글로벌 써야 함!

리스트는 괜춘