TIL1 | 완전 탐색 DFS BFS
기반 개념
- 탐색 search: 많은 양의 데이터 중 원하는 데이터를 찾는 과정
- 스택: 선입후출
- 큐: 선입선출
- 재귀 함수: 수학의 점화식을 소스코드로 옮긴 것. 점화식은 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것. 보통 점화식에서 종료 조건 찾을 수 있다.
함수는 메인 메모리의 스택에 저장되고, 마지막에 호출된 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료됨. 그러므로 재귀 함수 수행 = 스택 자료 구조 이용.
그래프 표현 방식
인접 행렬
2차원 배열. 연결 안된 노드끼리는 비용이 무한. 모든 관계를 저장하므로 노드 개수 많으면 메모리 낭비됨. but 연결 여부 빨리 탐색 가능
인접 리스트
linked list. 연결된 정보만 저장. 특정 노드와 연결된 모든 인접 노드를 순회해야 하는 경우 유리함.
DFS
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택 최상단 노드에 방문하지 않은 인접 노드 있으면 스택에 넣고 방문 처리 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 2를 반복한다.
시간복잡도 O(N)
BFS
- 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 큐에서 노드를 꺼내 해당 노드 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
- 2를 반복
시간복잡도 O(N)
최적해 보장. 주로 최단 거리 문제
2차원 배열 탐색 문제다? 그래프로 바꿔보자!
음료수 얼려먹기 - dfs
const ice = (n, m, map) => {
const board = map;
console.log(board);
const result = 0;
const dfs = (x, y) => {
if (x <= -1 || x >= n || y <= -1 || y >= m) {
return false;
}
if (board[x][y] === 0) {
board[x][y] === 1;
dfs(x - 1, y);
dfs(x + 1, y);
dfs(x, y - 1);
dfs(x, y + 1);
return true;
}
return false;
};
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (dfs(i, j) === true) {
result++;
}
}
}
return result;
};
const map = [
[0, 0, 1, 1, 0],
[0, 0, 0, 1, 1],
[1, 1, 1, 1, 1],
[0, 0, 0, 0, 0],
];
console.log(ice(4, 5, map));
미로찾기 - bfs
const solution = (n, m, board) => {
const queue = [];
//상하좌우
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
const vfs = (x, y) => {
queue.push([x, y]);
while (queue.length) {
const now = queue.shift();
x = now[0];
y = now[1];
for (let i = 0; i < 4; i++) {
let newX = x + dx[i];
let newY = y + dy[i];
if (newX < 0 || newX >= n || newY < 0 || newY >= m) continue;
if (board[newX][newY] === 0) continue;
if (board[newX][newY] === 1) {
board[newX][newY] = board[x][y] + 1;
queue.push([newX, newY]);
}
}
}
return board[n - 1][m - 1];
};
return vfs(0, 0);
};
const map = [
[1, 0, 1, 0, 1, 0],
[1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1],
];
console.log(solution(5, 6, map));
Author And Source
이 문제에 관하여(TIL1 | 완전 탐색 DFS BFS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hyseoseo/DFS-BFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)