2025-03-26
1. JavaScript로 BFS(너비 우선 탐색) 구현 및 설명
🔍 BFS란?
BFS (Breadth-First Search, 너비 우선 탐색): 그래프나 트리에서 가까운 노드부터 탐색하는 알고리즘
- 큐(Queue) 자료구조를 이용해서 방문할 노드를 저장하면서 진행
- 모든 인접 노드를 먼저 방문한 후, 다음 레벨(깊이)로 이동
- 최단 경로 문제에 자주 사용됨 (예: 미로 탐색, 최단 거리, 친구 추천 시스템)
🌟 BFS 구현 (JavaScript)
function bfs(graph, start) {
let queue = [start]; // BFS 탐색을 위한 큐 (FIFO)
let visited = new Set(); // 방문한 노드 저장 (중복 방지)
visited.add(start); // 시작 노드를 방문 처리
while (queue.length > 0) {
let node = queue.shift(); // 큐에서 첫 번째 원소(노드) 꺼내기
console.log(node); // 현재 노드 출력
// 현재 노드의 모든 인접 노드 탐색
for (let neighbor of graph[node]) {
if (!visited.has(neighbor)) { // 방문하지 않은 노드라면
visited.add(neighbor); // 방문 처리
queue.push(neighbor); // 큐에 추가
}
}
}
}
// 그래프 예제 (인접 리스트 방식)
const graph = {
1: [2, 3],
2: [4, 5],
3: [6, 7],
4: [],
5: [8],
6: [],
7: [],
8: []
};
// BFS 실행 (시작 노드: 1)
bfs(graph, 1);
그림으로 이해하는 BFS
예제 그래프
(숫자는 노드, 선은 간선)
1
/ \
2 3
/ \ \
4 5 6
/
8
📌 BFS 탐색 과정
| 단계 | 큐(Queue) | 방문 노드 |
| 초기화 | [1] | {1} |
| 1단계 | [2, 3] | {1, 2, 3} |
| 2단계 | [3, 4, 5] | {1, 2, 3, 4, 5} |
| 3단계 | [4, 5, 6] | {1, 2, 3, 4, 5, 6} |
| 4단계 | [5, 6] | {1, 2, 3, 4, 5, 6} |
| 5단계 | [6, 8] | {1, 2, 3, 4, 5, 6, 8} |
| 6단계 | [8] | {1, 2, 3, 4, 5, 6, 8} |
| 7단계 | [] (큐 비어있음) | {1, 2, 3, 4, 5, 6, 8} |
📌 BFS 원리 상세 설명
🔹 1. 큐(Queue) 사용
- `queue.shift()` → FIFO(First In First Out) 방식으로 노드 탐색
- 방문한 노드는 visited에 저장해서 중복 탐색 방지
🔹 2. 탐색 순서
- queue에서 꺼낸 노드의 모든 이웃 노드를 큐에 추가
- 가장 가까운 노드를 먼저 방문하고, 다음 레벨로 이동
- 깊이 우선 탐색(DFS)와 달리 한쪽으로 쭉 탐색하지 않고, 동심원처럼 퍼져나감
📌 BFS vs DFS 비교
| 알고리즘 | 자료구조 | 탐색 방식 | 사용 예시 |
| BFS | 큐(Queue) | 가까운 노드부터 탐색 | 최단 경로 문제, 네트워크 탐색 |
| DFS | 스택(Stack) (재귀) | 한 경로 끝까지 탐색 후 백트래킹 | 미로 탐색, 백트래킹 |
✅ BFS는 최단 경로 탐색에 유리
✅ DFS는 모든 경우의 수 탐색에 유리
📌 시간 복잡도
- BFS의 시간 복잡도는 O(V + E)
- V : 노드(정점, Vertex)의 개수
- E : 간선(Edge)의 개수
- 모든 노드를 한 번씩 방문하며, 인접 리스트에서 모든 간선을 확인하기 때문!
🎯 정리
✅ BFS는 가까운 노드부터 탐색하는 알고리즘
✅ 큐(Queue) 사용 & 방문 체크를 위한 Set 활용
✅ 최단 경로 찾을 때 유리
✅ 시간 복잡도는 `O(V + E)`
✅ DFS와 비교하면 BFS는 한 번에 넓게 탐색
2. BFS가 필요한 문제 패턴
| BFS를 사용해야 하는 특징 | 설명 |
| 최소 횟수(최단 거리) 문제 | 가장 적은 이동 횟수로 도달하는 문제 |
| 동시에 퍼지는 문제 | 여러 지점에서 동시에 전파되는 구조 |
| 2차원 격자에서의 이동 | 미로 탐색, 지도 탐색, 감염 확산 등 |
🚀 "이 문제 BFS로 풀어야겠네!" 판단하는 공식
- 최단 거리(최소 횟수)를 구하는가?
- 여러 개의 시작점에서 동시에 퍼지는가?
- 격자(2D 배열)에서 상하좌우 이동하는가?
✔ 3가지 중 하나라도 해당하면 BFS 고려
✔ 2개 이상 해당하면 BFS가 거의 정답!
3. 프로그래머스 음양마스터
function solution(absolutes, signs) {
var answer = 0;
for(let i = 0; i < absolutes.length; i++){
if(signs[i]){
answer += absolutes[i];
} else {
answer -= absolutes[i];
}
}
return answer;
}뭔가 `reduce`를 쓸 수 있을 것 같은데 두 가지 조건 분기처리를 어떻게 해야할지 가늠이 안 돼서 for문으로 풀었다.
모범답안을 살펴보니 `reduce`만 사용하면 되는 게 아니라, 삼항연산자를 함께 사용해야 했다.
function solution(absolutes, signs) {
return absolutes.reduce((answer, num, i) => answer + num * (signs[i] ? 1 : -1), 0)
}
4) 거래소 수수료 집계 - 타입 selectbox 오류 수정
✅ 에러
- 1. 기존에 저장된 코드값을 지우면, 해당 코드값을 기반으로 생성된 selectbox 항목에 null 뜨는 오류 (원래대로라면, null 값이 뜨는 대신 그냥 항목이 추가되지 않아야 함)
- 2. 이전에 pinia store에서 기본값 강제 세팅했던 부분에서 오류가 남 👉 배열이 5개씩 그냥 화면에 띄워지고 있었음.
✅ 원인 & 해결
- 1. selecbox 항목으로 nll 뜨는 이유는 기존에 존재하던 데이터를 전부 삭제하고 저장 버튼을 누르면 `{ko: null}` 👉 이런 식으로 데이터가 서버로 넘어갔고, 이로 인해서 서버에서도 null 값을 보내주어 항목명이 변경된 것. 이를 방지하기 위해 (데이터가 1개 있는 경우 && code, ko(필수값) 입력되지 않은 경우) 빈 배열로 대체해서 값을 서버로 보내줌
- 2. 빈 input field가 여러 개 띄워지는 문제의 원인: 항목이 비어있을 때 강제로 들어가게 세팅했던 기본값과, 값을 selectbox에 넣기 위해 변환하는 함수의 input 값의 포맷이 달랐다... 값은 제대로 함수에 넘어가는데, 포맷이 다르다 보니 값을 제대로 변환할 수 없어서 null이 떴던 것. 강제로 세팅했던 기본값을 삭제해줌으로써 문제가 해결되었다.
5) 코드 타입에 따라 우클릭 메유(이벤트 리스너) 내부 항목 노출여부 결정
grid 컴포넌트에서 `headerId` 받아와서 현재 클릭한 컬럼의 타입을 계산했다.
이후에 이벤트 리스너에 v-if 붙여 타입별로 렌더링해주었다.
