탐색이란 ? - 많은 양의 데이터 중에서 원하는 데이터를 찾는 것
사전 지식 1) 스택 자료구조 (박스 쌓기) 2. 큐 자료구조 ( 파이썬에선 deque 활용) 3) 재귀함수
* 재귀함수 (Recursion Function) : 자기 자신을 다시 호출
def recursive(i):
recursive(i)
#재귀함수는 종료조건을 반드시 명시해야한다.
if i == 100:
return
#팩토리얼 함수
def factorial(n):
if n<=1:
return 1
return n * factorial(n-1)
#최대 공약수
def gcd(a,b) #a>b
if a % b == 0
return b
else:
return gcd(b,a%b)
* DFS ( Depth First Search)
- 깊이 우선 탐색
- 그래프의 깊은 부분을 우선 탐색
- DFS는 스택자료구조 or 재귀함수를 사용한다
1. 탐색 시작 노드를 스택에 삽입, 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문처리한다.
방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다
3. 더이상 2번을 수행할 수 없을 때까지 반복
# 음료수 먹기 - 0이 2개이상 인접한 것 찾기
상 하 좌 우
값이 0 이면서 아직 방문하지 않은 지점
--------------추가-------------------------------------------------------------
DFS 문제를 파이썬으로 풀 때 가장 중요한 점
1)
import sys sys.setrecursionlimit(10000) : 런타임 오류의 주범 중 하나. 무족권 써놓자
2)
dfs에는 두 가지의 형태가 존재한다
* 행렬이 주어지거나 2차원 그래프 형태로 주어진다면 행렬 형태를 사용하여 탐색한다.
* 일차원 그래프 형태로 주어진다면 인접리스트를 구현하여 최적화형태로 만들어 푸는 것이 좋다.
행렬 문제 - 1012번
인접리스트 문제 - 11724번
PS) input()대신 stdin.readline()를 쓴다면 시간을 대폭 줄일 수 있다!
11724, 1012, 1743, 2667, 2583, 10026, 11403(★), 2468(★), 10552, 9466, 10265(★)
2606