- 스택: FILO, 선입 후출, append와 pop 모두 같은 입구에서
stack[::-1] : 거꾸로 출력- 큐: FIFO, 선입 선출, append -> ======= -> pop
from collections import deque
queue = deque()
#삽입(5-2-3-7) 삭제(popleft) 삽입(1-4) => 삭제(popleft)
= [5,2,3,7] => [2,3,7] => [2,3,7,1,4] => [3,7,1,4]
queue.append()
queue.popleft()
queue.reverse()- 재귀함수
#유클리드 호제법 (최대 공약수 구하기)
def gcd(a,b):
if a%b == 0:
return b
else:
gcd(b, a%b)DFS
깊이 우선 탐색, 깊은 부분부터 우선적으로 탐색
-> 스택, 재귀함수 이용
1. 탐색 시작 노드를 스택에 삽입, 방문처리
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리
3. 더 이상 2번의 과정을 수행할 수 없을 때까지
1과 인접한 2, 3 중 작은 숫자 2 선택
2와 인접한 노드 7 선택
7과 인접한 노드 6과 8중 6 선택
6과 인접한 노드 X => 6 pop
7과 인접한 노드 8
8과 인접한 노드 X => 8 pop
7과 인접한 노드 X => 7 pop
2과 인접한 노드 X => 2 pop
1과 인접한 노드 3 선택
3과 인접한 노드 4,5 중 4 선택
4와 인접한 노드 5 선택
1->2->7->6->8->3->4->5
def dfs(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in graph[v]:
if not visited[v]:
dfs(graph, i, visited)
graph = [
[], #시작이 1부터인 경우가 많기 때문에 비워둠
[2,3,5] #1번 노드와 연결
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False] * 9
dfs(graph, 1, visited)
BFS
너비 우선 탐색, 그래프에서 가까운 노드부터 우선적으로 탐색
= 큐 자료구조 이용
- 탐색 시작 노드를 큐에 삽입, 방문처리
- 큐에서 노드를 꺼낸 귀에 해당 노드의 인접 노드 중에는 방문하지 않은 노드를 모두 큐에 삽입
- 1과 인접한 노드 = [2,3,8]
- 2와 인접한 노드 = [1,7]
- 3과 인접한 노드 = [1,4,5]
- 8과 인접한 노드 = [1,7]
- 7과 인접한 노드 = [2,6,8]
- 4와 인접한 노드 = [3,5]
- 5와 인접한 노드 = [3,4]
- 6과 인접한 노드 = [7]
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
graph = [
[], #시작이 1부터인 경우가 많기 때문에 비워둠
[2,3,5] #1번 노드와 연결
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False] * 9
bfs(graph, 1, visited)BFS DFS 구별
BFS (Breadth-First Search)
너비 우선 탐색으로, 그래프에서 가장 가까운 노드부터 탐색하는 알고리즘입니다.
최단 경로를 찾는 문제에서 사용할 수 있습니다.
노드의 깊이가 얕은 경우 (예: 레벨이 적은 경우)에 유리합니다.
구현이 상대적으로 간단하고, 해가 존재하는 경우에는 보통 더 빠르게 찾을 수 있습니다.
그러나 노드의 깊이가 깊은 경우 (예: 레벨이 많은 경우)에는 DFS에 비해 메모리를 많이 사용하게 됩니다.
DFS (Depth-First Search)
깊이 우선 탐색으로, 그래프에서 가장 깊은 노드부터 탐색하는 알고리즘입니다.
그래프에서 모든 노드를 탐색하거나, 경로를 찾는 문제에서 사용할 수 있습니다.
노드의 깊이가 깊은 경우 (예: 레벨이 많은 경우)에 유리합니다.
구현이 상대적으로 복잡하고, 노드의 깊이가 얕은 경우에는 BFS에 비해 더 오래 걸릴 수 있습니다.
그러나 메모리를 덜 사용하게 됩니다.
따라서, BFS는 최단 경로를 찾는 문제에서, DFS는 모든 경로를 찾는 문제에서 사용할 수 있습니다. 그러나 상황에 따라 BFS와 DFS 중 적절한 알고리즘을 선택하는 것이 중요합니다.
백트래킹
if start not in graph: # 출발지에서 더 이상 갈 수 있는 항공권이 없는 경우
return None
for i, end in enumerate(graph[start]): # 현재 출발지에서 갈 수 있는 모든 도착지에 대해
graph[start].pop(i) # 사용한 항공권을 그래프에서 삭제
result = dfs(end, route + [end]) # 재귀적으로 다음 도착지를 찾아 경로를 구함
if result: # 모든 항공권을 사용한 경로를 찾은 경우
return result
graph[start].insert(i, end) # 그래프를 원상태로 복구시키기 위해 항공권 정보를 다시 삽입
해당 경로로는 더 이상 방문할 수 있는 도시가 없는 경우, 방문한 end를 다시 graph에 추가해주는 과정을 거쳐서, 이전 경로에서 다른 도시를 선택해서 탐색할 수 있도록 합니다. 이렇게 하면 모든 경로를 탐색할 수 있으며, 모든 경로 중에서 알파벳 순으로 가장 빠른 경로를 찾을 수 있습니다.
