DFS
깊이 우선 탐색 (Depth First Search)
너비보다 깊이를 우선적으로 탐색하기에, 뻗어나간 노드 중 하나를 깊게 탐색하고, 다시 되돌아와 옆 노드 또한 같은 작업을 반복한다.
깊은 노드에 해가 있을 때 유리하다.
(stack, 재귀 사용)
시간복잡도:
- 인접리스트:
O(|V| + |E|)- 인접행렬:
O(V^2)
(V: 정점의 개수,E: 간선의 개수)
장점
경로상의 노드만 기억하면 되므로 저장공간 수요가 적다.
목표가 경로의 깊은 곳에 위치하면 비교적 빨리 탐색 가능하다.
단점
DFS의 결과가 최단 경로라는 보장이 없다.
답이 아닌 경로가 매우 길거나 무한하면, 그 경로를 계속 파고들어야하기 때문에 비효율적이다.
DFS 사용유형
- 하나의 정점과 연결된 모든 정점을 탐색하는 경우
- 경로를 찾아야 하는 경우
- 사이클이 존재하는 경로를 찾는 경우
(참고: https://myeongmy.tistory.com/55)
DFS 구현
with js
const graph = [[],[2,3],[1,4,5],[1,6],[2],[2],[3]]
const visited = new Array(graph.length).fill(false);
function dfs(graph,node,visited){
visited[node] = true;
console.log(node)
graph[node].map(n=> !visited[n] && dfs(graph,n,visited))
}
dfs(graph,1,visited)BFS
너비 우선 탐색 (Breadth First Search)
인접한 노드 순서대로 탐색하고, 점차 깊이를 늘려나가며 탐색한다.
노드의 수가 적고, 얕은 노드에 해가 존재할 때 유리하다.
(queue 사용)
시간복잡도:
- 인접리스트:
O(|V| + |E|)- 인접행렬:
O(V^2)
(V: 정점의 개수,E: 간선의 개수)
장점
BFS의 결과는 항상 최단거리를 보장한다.
단점
최악의 경우(인접한 노드중 가장 마지막 순서인 경우), 탐색이 가장 오래 걸린다.
BFS 사용유형
- 최단 거리를 구하는 경우
- 최단 거리를 구하지만 방문한 지점도 다시 방문하는 경우
(참고: https://myeongmy.tistory.com/55)
BFS 구현
with js
const graph = [[], [2, 3], [1, 4, 5], [1, 6], [2], [2], [3]];
const visited = new Array(graph.length).fill(false);
function BFS(node, graph, visited) {
const queue = [node];
visited[node] = true;
while (queue.length) {
let temp = queue.shift();
console.log(temp);
graph[temp].map((el) => {
if (!visited[el]) {
queue.push(el);
visited[el] = true;
}
});
}
}
BFS(1, graph, visited);그래프의 인접 행렬과 인접 리스트
인접 행렬
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 0 | 0 | 0 |
| 2 | 1 | 0 | 0 | 1 | 1 | 0 |
| 3 | 1 | 0 | 0 | 0 | 0 | 1 |
| 4 | 0 | 1 | 0 | 0 | 1 | 0 |
| 5 | 0 | 1 | 0 | 0 | 0 | 0 |
| 6 | 0 | 0 | 1 | 0 | 0 | 0 |
활용 예시
- 폴로이드 워셜 알고리즘
인접 리스트
활용 예시
- 다익스트라 알고리즘
- 프림 알고리즘
문제
https://programmers.co.kr/learn/courses/30/lessons/1844
접근
전형적인 최단거리 문제로, 현재 위치를 기반으로 상하좌우로 움직이면서 거리를 늘려나간다.
문제풀이
1. rows, columns, 상하좌우 세팅
const dx = [-1,0,1,0]
const dy = [0,1,0,-1]
const row = maps.length;
const col = maps[0].length;2. BFS를 돌리며 조건에 맞는(막히지 않은 인접한 길) 칸을 방문한다.
const queue = [[0,0]];
while(queue.length){
const [y,x] = queue.shift();
for(let i=0;i<4;i++){
const nx = x+dx[i];
const ny = y+dy[i];
if(nx>=0 && ny>=0 && nx<col && ny<row){
if(maps[ny][nx]===1){
maps[ny][nx] = maps[y][x]+1
queue.push([ny,nx])
}
}
}
}3. 최종 결과 출력
return maps[row-1][col-1]===1 ? -1 : maps[row-1][col-1]전체 코드
function solution(maps) {
var answer = 0;
const dx = [-1,0,1,0]
const dy = [0,1,0,-1]
const row = maps.length;
const col = maps[0].length;
const queue = [[0,0]];
while(queue.length){
const [y,x] = queue.shift();
for(let i=0;i<4;i++){
const nx = x+dx[i];
const ny = y+dy[i];
if(nx>=0 && ny>=0 && nx<col && ny<row){
if(maps[ny][nx]===1){
maps[ny][nx] = maps[y][x]+1
queue.push([ny,nx])
}
}
}
}
return maps[row-1][col-1]===1 ? -1 : maps[row-1][col-1]
}참고
- DFS,BFS 개념과 구현: https://jeinalog.tistory.com/18
- DFS,BFS 장단점: https://soobarkbar.tistory.com/61
- 코딩테스트 문제 유형 별 풀이법: https://myeongmy.tistory.com/55
꾸준하게 공부하기