그래프 탐색 알고리즘 : DFS/BFS
스택 자료구조
- 먼저 들어 온 데이터가 나중에 나가는 형식의 자료구조.
- 입구와 출구가 동일한 형태.
스택을 구현하기위해서 단순히 리스트를 사용한다.
- 가장 오른쪽에서 원소를 삽입하는 append 메서드
- 가장 오른쪽에서 원소를 꺼내는 pop 메서드
두 함수의 시간복잡도는 상수시간 O(1)
최상단 원소부터 출력 : print(stack[::-1])
최하단 원소부터 출력 : print(stack)
- Extended Slices : 배열의 index에 접근하는 방법으로 arr[A:B:c]의 의미는, index A 부터 index B 까지 C의 간격으로 배열을 만들어라는 말이다. [::-1]은 처음부터 끝까지 -1간격으로 출력(역순으로)
큐 자료구조
- 먼저 들어 온 데이터가 먼저 나가는 형식의 자료구조.
- 큐는 입구와 출구가 모두 뚫려 있는 형태.
큐를 구현하기 위해서는 덱(deque)라이브러리를 사용할 수 있다.
- 원소를 삽입할때는 append()
- 원소를 삭제할때는 popleft()
엄밀히 말하면 덱 라이브러리는 스택과 큐의 장점을 모두 가지는 라이브러리
append()는 리스트에서와 같이 동작한다. popleft() 가장 왼쪽에 원소를 꺼낼때 사용
먼저 들어온 순서대로 출력 : print(queue)
역순으로 바꾸기 : queue.reverse() 후에 print
재귀함수
- 재귀함수(Recursive Function)란 자기자신을 다시 호출하는 함수
- DFS를 실질적으로 구현하고자할때 자주 사용된다.
간단한 예시
def recursive_function():
print('재귀 함수를 호출합니다.')
recursive_function()
recursive_function()- 파이썬에서는 최대 재귀 깊이제한이 있기때문에 오류메세지가 출력될 수 있다.
-재귀함수를 문제 풀이에서 사요할 때는 종료 조건을 반드시 명시해야 한다.
def recursive_function(i):
# 100번째 호출을 했을 때 종료되도록 종료 조건 명시
if i == 100:
return
print(i, '번째 재귀함수에서', i+1, '번째 재귀함수를 호출합니다.')
recursive_function(i+1)
print(i, '번쨰 재귀함수를 종료합니다.')
recursive_function(1)최대공약수
두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 합시다.
이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다.
def gcd(a, b):
if a % b == 0:
return b
else:
return gcd(b, a % b)
print(gcd(192, 162))DFS
- 깊이 우선 탐색
- 스택 or 재귀함수를 이용
DFS 소스코드 예제
# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7],
]
# 각 노드가 방문된 정보를 표현 (1차워 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출
dfs(graph, 1, vistied)-
인덱스 1 부터 시작하는 경우가 많기 때문에 0번 인덱스는 빈리스트로 비워두고
1번 인덱스부터 해당 노드에 인접한 리스트 방식으로 표현 -
방문한 리스트 처리를 위해 1차원 리스트를 만들 False 로 초기화해 하나도 방문하지 않은것으로 만들어준다. 그리고 1번 노드부터 8번 노드까지 가지고 있고 인덱스 0은 사용하지 않기 위해서 하나 더 큰 크기로 1차원리스트를 초기화 할 수 있다.
dfs 함수 정의
def dfs(graph, v, visited):
# 현재 노드를 방문 처리
vistied[v] = True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)(for문을 돌때 리스트의 인덱스를 i 로 돈다고 생각해서 한참 해맸다..)
프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있다.
1. 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식
2. 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식
BFS
- 너비 우선 탐색
- 큐 자료구조
- 최단거리문제에서 사용된다.
bfs 함수 정의
from collections import deque
#BFS 메서드 정의
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
TIL 정리