쏭의 개발 블로그
[2] DFS & BFS 본문
탐색(Search)
- 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
- DFS, BFS → 코딩테스트에서 매우 자주 등장하는 유형(반드시 숙지!!!)⭐
DFS/BFS를 위해 반드시 알아야할 자료구조
✏️ 스택
- 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조
- 입구와 출구가 동일한 형태로 시각화
- 삽입, 삭제 2가지 연산으로 구성
파이썬 구현
- 리스트 자료구조 사용
stack=[]
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()
print(stack[::-1]) # 최상단 원소부터 출력 (먼저 나가고자하는 원소부터)
print(stack) # 최하단 원소부터 출력
# [1,3,2,5]
# [5,2,3,1]
자바 구현
import java.util.*;
public class Main {
public static void main(String[] args){
Stack<Integer> S = new Stack<>();
s.push(5);
s.push(2);
s.push(3);
s.push(7);
s.pop();
s.push(1);
s.push(4);
s.pop();
while(!s.empty()) {
System.out.print(s.peek() + " ");
s.pop();
}
}
}
✏️ 큐
- 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조
- 입구와 출구가 모두 뜷려 있는 터널과 같은 형태로 시각화
파이썬 구현
- deque 라이브러리 이용
from collections import deque
# 큐 구현을 위해 deque 라이브러리 이용
queue=deque()
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5) # 오른쪽에 추가
queue.append(2) # 빼는 것
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()
print(queue) # 먼저들어온 순서대로 출력 # deque([3,7,1,4])
queue.reverse()
print(queue) # 나중에 들어온 원소부터 출력 # deque([4,1,7,3])
자바 구현
import java.util.*;
public class Main {
public static void main(String[] args){
Queue<Integer> q = new LinkedList<>();
// 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
q.offer(5);
q.offer(2);
q.offer(3);
q.offer(7);
q.poll();
q.offer(1);
q.offer(4);
q.poll();
// 먼저 들어온 원소부터 추출
while (!q.isEmpty()){
System.out.print(q.poll()+" ");
}
}
}
✏️ 재귀함수(Recursive Function)
- 자기 자신을 다시 호출하는 함수
- 파이선에서 최대 재귀 깊이 제한 → 최대 재귀 깊이 초과 메세지 출력
단순한 형태의 재귀함수 예제
def recursive_function():
print('재귀함수 호출')
recursive_function()
recursive_function()
- 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야함
- 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있음
종료조건을 포함한 재귀함수 예제
def recursive_function(i):
# 100번째 호출을 했을 때 종료되도록 종료조건 명시
if i==100:
return
print(i, '번째 재귀함수에서' i+1, '번째 재귀함수를 호출합니다')
recursive(i+1)
print(i,'번째 재귀함수를 종료합니다')
recursive_funtion(1)
# 1~100번째 호출
# 99~1 종료
팩토리얼 구현 예제
# 반복적으로 구현한 n!
def factorial_iterative(n):
result=1
# 1부터 n까지의 수를 차례대로 곱하기
for i in range(1,n+1):
result *= i
return result
# 재귀적으로 구현한 n!
def factorial_recursive(n):
if n<=1: # n이 1이하인 경우 1을 반환
return 1
# n! = n * (n-1)! 을 코드로 구현
return n * factorial_recursive(n-1)
# n! 출력
print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_recursive(5))
유클리드 호제법 예제
- 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘
- 유클리드 호제법
- 두 자연수 A, B에 대해 (A>B) A를 B로 나눈 나머지를 R이라고 하자
- A와 B의 최대공약수는 B와 R의 최대공약수와 같다
- 유클리드 호제법의 아이디어를 그대로 재귀함수에 작성
- GCD(192,162)A B
192 162 162 30 30 12 12 6
- GCD(192,162)A B
- 코드
def gcd(a,b):
if a%b==0:
return b
else:
return gcd(b,a%b)
print(gcd(192,162))
💡 재귀 함수 사용의 유의사항
- 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성 가능
- 다른 사람이 이해하기 어려운 코드가 될 수 있으므로 신중하게!
- 모든 재귀함수는 반복문을 이용하여 동일한 기능 구현 가능
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 내부의 스택 프레임이 쌓임
- 스택을 사용 시 스택 라이브러리 대신에 재귀함수 사용하는 경우
💡DFS (Depth-First Search)
- 깊이 우선 탐색
- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- 스택 자료구조(재귀함수) 이용
- 탐색 시작 노드를 스택에 삽입, 방문처리
- 스택의 최상단 노드의 인접노드 확인
- 방문하지 않은 인접 노드가 하나라도 있음 : 그 노드를 스택에 넣고 방문 처리
- 방문하지 않은 인접 노드가 없음 : 스택에서 최상단 노드를 꺼냄
- 2번의 과정을 수행할 수 없을 때까지 반복
파이썬 코드
# DFS 메서드 정의
def dfs(graph, v, visited):
# 현재 노드를 방문 처리
visited[v]=True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph=[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9 # index 0을 사용하지 않기 위해 9개 선언
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)
자바 코드
import java.util.*;
public class Main {
public static boolean[] visited = new boolean[9];
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
public static void dfs(int x){
//현재 노드 방문 처리
visited[x]=true;
System.out.print(x+" ");
// 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for (int i=0; i < graph.get(x).size(); i++) {
int y=graph.get(x).get(i);
if (!visited[y]) dfs(y);
}
}
public static void main(String[] args){
// 생략
}
}
💡BFS (Breadth-First Search)
- 너비 우선 탐색
- 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
- 큐 자료구조
- 탐색 시작노드를 큐에 삽입하고 방문처리
- 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
- 2번의 과정을 더이상 수행할 수 없을 때까지 반복
파이썬 코드
from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited):
# 큐 구현을 위해 deque 라이브러리 사용
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
# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph=[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9 # index 0을 사용하지 않기 위해 9개 선언
# 정의된 DFS 함수 호출
bfs(graph, 1, visited)
자바 코드
import java.util.*;
public class Main {
public static boolean[] visited = new boolean[9];
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
public static void bfs(int start){
Queue<Integer> q= new LinkedList<>();
q.offer(start);
//현재 노드 방문 처리
visited[start]=true;
// 큐가 빌 때까지 반복
while(!q.isEmpty()) {
// 큐에서 하나의 원소를 뽑아 출력
int x=q.poll();
System.out.print(x+" ");
// 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for (int i=0; i < graph.get(x).size(); i++) {
int y=graph.get(x).get(i);
if (!visited[y]) {
q.offer(y);
visited[y]=true;
}
}
}
}
// 메인 함수 생략
}
출처 : https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3
'알고리즘' 카테고리의 다른 글
[6-1] 최단거리 알고리즘 - 다익스트라 알고리즘 (0) | 2023.06.25 |
---|---|
[5] 다이나믹 프로그래밍 (0) | 2023.02.28 |
[4] 이진탐색 (0) | 2023.02.28 |
[3] 정렬 알고리즘 (0) | 2023.02.28 |
[1] 그리디 & 구현 (0) | 2023.01.30 |