탐색-DFS

탐색은 주어진 데이터에서 원하는 데이터를 찾아내는 알고리즘을 말한다.
DFS , BFS , 이진탐색이 있다.

이론

📖 DFS (깊이우선탐색)

• 그래프 완전 탐색기법 중 하나.
• 그래프의 시작노드에서 출발하여 탐색할 한 쪽 분기를 정해, 최대 깊이까지 탐색을 끝낸 후 다른쪽 분기로 이동해 다시 탐색을 진행하는 과정을 반복한다.
• 시간복잡도 : O(V+E) , V는 노드수를 E는 에지 수를 의미한다.
• 재귀함수로 구현. -----> 스택 오버플로우에 유의.
• 스택 자료구조 이용.
• 유형) 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상정렬 등

• DFS 탐색방식은 후입선출 특성을 통해 스택 을 사용한다.
• 위의 <그림>에서 탐색순서는 1->3->4->6->2->5 가 된다.

문제풀이

• 그래프를 인접리스트로 표현하기.
• 방문리스트 작성하기.

📖 백준 11724 (🔗백준 11724 문제)

✏ 연결요소는 에지로 연결된 노드의 집합. 한 번의 DFS가 끝날 때까지 탐색한 모든 노드의 집합을 하나의 연결요소로 판단.

✏ 연결요소의 개수 = 모든 노드를 탐색하는 데 실행한 DFS의 실행횟수.

• 그래프의 데이터를 인접리스트로 저장.
• 방문리스트(초기 : "F"로 구성) 작성.

#연결요소 = 에지로 연결된 노드의 집합, DFS가 끝날때까지 탐색한 모든 노드의 집합을 하나의 연결요소로 판단.
#DFS 총 N번 수행 -> 연결요소개수 = 2개

import sys
sys.setrecursionlimit(10000)
input=sys.stdin.readline

n,m=map(int,input().split())
arr=[[] for i in range(n+1)]
visit=[0]*(n+1)
count=0

def DFS(n):
	visit[n]=1
	for i in arr[n]:
		if not visit[i]:
			DFS(i)
		
for i in range(m):
	u,v=map(int,input().split())
	arr[u].append(v)
	arr[v].append(u)

for i in range(1,n+1):
	if not visit[i]:
		count+=1
		DFS(i)

print(count)		

📖 백준 2023 (🔗 백준 2023 문제)

✏ 소수판별함수, DFS 함수 작성.

📍 시간초과에 유의 -> 소수판별함수 작성에 주의.

#소수는 약수가 1과 자기 자신인 수.

import sys
sys.setrecursionlimit(10000)
input=sys.stdin.readline

n=int(input())

def prime(num):
	for i in range(2,int(num/2+1)):
		if(num%i==0):
			return False
	return True

def DFS(a):
	if(len(str(a))==n):
		print(a)
	else:
		for i in range(1,10):
			if (i%2==0):
				continue
			if (prime(a*10+i)):
				DFS(a*10+i)

# 일의 자리 소수 (2,3,5,7)

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

◼ 참고사항

• Do it! 알고리즘 코딩테스트
• 백준