BFS, 너비 우선 탐색BFS(너비 우선 탐색, Breadth-First Search)은 그래프 혹은 트리에서 한 노드(정점)로부터 시작하여 가까운(직접 연결된) 노드부터 차례대로 방문하는 알고리즘입니다. 즉, 루트 노드(시작 노드)에 인접한 노드들을 먼저 모두 탐색한 뒤, 그다음 레벨의 노드들을 방문하는 방식입니다. 특징큐(Queue)를 사용 : 먼저 들어온 노드를 먼저 처리하는 FIFO 구조.계층(Level) 기반 탐색 : 시작 노드로부터 거리가 같은 노드들을 먼저 모두 방문.방문 기록(Visited) 필요 : 무한 루프 방지 및 중복 탐색 방지를 위해 방문 여부를 저장.시간 복잡도 O(V + E) : V는 노드 수, E는 간선 수이며, 모든 노드와 간선을 한 번씩만 확인. 활용 분야가중치가 없는 그..

Link2667번 - 단지 번호 붙이기 문제풀이(1) DFS 재귀let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");let idx = 0;const N = Number(input[idx++]);const map = Array.from({ length: N }, () => []);const visited = Array.from({ length: N }, () => Array.from({ length: N }, () => false));const answers = [];const dr = [0, 1, 0, -1];const dc = [1, 0, -1, 0];for (let n = 0; n { visited[..

Link2468번 - 안전 영역 문제풀이(1) DFS 재귀 구현let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");let idx = 0;const N = Number(input[idx++]);const map = [];let maxAnswer = 0;const dn = [0, 1, 0, -1];const dm = [1, 0, -1, 0];for (let n = 0; n { return n = N || m >= N;};const dfsRecursive = (n, m, visited, value) => { visited[n][m] = true; for (let d = 0; d Array.from({..

Link11724번 - 연결 요소의 개수 문제풀이(1) 재귀 구현let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");let idx = 0;const [N, M] = input[idx++].split(" ").map(Number);const graph = Array.from({ length: N + 1 }, () => []);const visited = Array.from({ length: N + 1 }, () => false);let answer = 0;for (let m = 0; m { visited[node] = true; for (let g of graph[node]) { if (visited..

Link1012번 - 유기농 배추 문제풀이(1) DFS 재귀let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");let idx = 0;const T = Number(input[idx++]);const dn = [0, 1, 0, -1];const dm = [1, 0, -1, 0];const answer = Array.from({ length: T }, () => 0);for (let t = 0; t Array.from({ length: M }, () => false) ); const visited = Array.from({ length: N }, () => Array.from({ length: M..

Link2606번 - 바이러스 문제풀이(1) 재귀 DFSvar input = require("fs") .readFileSync("/dev/stdin") .toString() .trim() .split("\n");const N = Number(input[0]);const graph = Array.from({ length: N + 1 }, () => []);for (let i = 2; i (2) 스택 DFSvar input = require("fs") .readFileSync("/dev/stdin") .toString() .trim() .split("\n");const N = Number(input[0]);const graph = Array.from({ length: N + 1 }, () =>..

Link11725번 - 트리의 부모 찾기 문제풀이(1)var input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");const N = Number(input[0]);let graph = Array.from({ length: N + 1 }, () => []);// 트리의 간선은 N-1개이므로 해당 줄만 처리for (let i = 1; i (2)var input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");const N = Number(input[0]);let graph = Array.from({ length: N + 1 }, () => ..

DFS, 깊이 우선 탐색DFS란?Depth-First Search의 약자이자 깊이 우선 탐색으로 부르며, Graph (그래프)에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. 즉, 그래프의 루트 노드(혹은 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 간단하게는 시작 노드에서 출발하여, 한 방향으로 갈 수 있을 때까지 깊이 탐색한 뒤 더 이상 갈 수 없으면 직전에 방문했던 노드로 되돌아가 다른 경로를 탐색하는 방식이라고 할 수 있습니다.  특징깊이 우선으로 진행 : 갈 수 있는 곳까지 재귀적으로(또는 스택을 사용하여) 끝까지 들어간 뒤, 더 이상 진행할 수 없으면 되돌아노는 방식트리 구조나 그래프 모두 탐색 가능방문 기록(visited ..

Link코딩테스트 연습 - 햄버거 만들기 문제풀이(1)function solution(ingredient) { const stack = []; let hamburgerCount = 0; for (let ing of ingredient) { stack.push(ing); // stack의 마지막 4개 재료가 [1, 2, 3, 1] 인지 확인 if ( stack.length >= 4 && stack[stack.length - 4] === 1 && stack[stack.length - 3] === 2 && stack[stack.length - 2] === 3 && stack[stack.length - 1] === 1 ) { ..

Link코딩테스트 연습 - 숫자 짝꿍 문제풀이(1)function solution(X, Y) { const countX = new Array(10).fill(0); const countY = new Array(10).fill(0); for (const ch of X) { countX[parseInt(ch)]++; } for (const ch of Y) { countY[parseInt(ch)]++; } let result = ""; for (let digit = 9; digit >= 0; digit--) { const commonCount = Math.min(countX[digit], countY[digit]);..