일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 백준 js
- useEffect return
- 투포인터알고리즘 js
- 머쓱이
- 프로그래머스 데브코스 프론트엔드
- react 프로젝트 리팩토링
- Vue3
- 백준 node.js
- 모던 자바스크립트 Deep Dive
- Vue3 Router
- 리팩토링 회고
- 모던 javascript Deep Dive
- 프로그래머스 K_Digital Training
- KDT 프로그래머스
- K_Digital Training
- 모던 자바스크립트 딥다이브
- TypeScript 문법 소개
- 모던 자바스크립트 Deep Dive TIL
- 우테캠 회고록
- frontend roadmap study
- 프로그래머스 데브코스
- KDT 프로그래머스 데브코스 프론트엔드
- react customHook 예시
- 개발자 특강
- useRef 지역 변수
- Frontend Roadmap
- 프로그래머스 K_Digital Training 프론트엔드
- 인프런 자바스크립트 알고리즘 문제풀이
- 프로그래머스 데브코스 프론트엔드 TIL
- 모던 자바스크립트 TIL
- Today
- Total
목록알고리즘_JS/백준_Graph(DFS,BFS) (13)
프론트엔드 개발자의 기록 공간
백준 DFS 알고리즘 2667번_단지번호붙이기 난이도 : 실버I 문제 설명 문제 풀이 : 이 문제도 기본 DFS 유형을 요구하는 문제이다. 그래프 전체를 순회하면서 방문하지 않았다면 (이 문제에서 1과 0은 아파트의 위치이면서 방문여부로도 활용할 수 있다.) DFS를 호출한다. 여기서 DFS내부적으로 재귀를 부를때마다 선언해둔 글로벌 변수(home)를 한개씩 카운트 해주면서 같은 단지내의 아파트 개수를 세려주고 DFS함수 호출이 끝나면 하나의 단지를 탐색한 것이기 때문에 순서대로 배열에 넣어주면된다. 이후 정렬을 하고 길이 출력을 통해 단지 개수를 파악하고 배열값을 출력하면서 단지내 아파트 개수를 출력하면 된다. //실버1 단지번호붙이기 const solution = () => { let cnt = []..
백준 DFS 알고리즘 4963번_섬의 개수 난이도 : 실버II 문제 설명 입출력 문제 풀이 : 1012_유기농 배추부분이랑 로직은 일치한다. 관련된 로직은 (ghost4551.tistory.com/27) 여기에 상세하게 설명해뒀으니 참고하면 좋을것같다. 한번더 설명하자면 DFS를 활용하여 연결된 요소를 방문처리하고 연결된 집합의 개수를 출력해주면 된다. 여기서 고려해야될게 방문처리는 그래프의 값을 0으로 초기화 시켜 해결할 수 있다. 또한 대각선 이동도 유의해야한다. //실버2 섬의 개수 const solution = () => { //별 섬의 개수 let cnt = 0; //가로 세로 배열 높이 구하기 [w, h] = input .shift() .split(" ") .map((el) => Number(..
백준 DFS 알고리즘 1012번_유기농 배추 난이도 : 실버II 문제 설명 입출력 문제 풀이 : 이 문제는 백준 11724번 연결 요소의 개수 문제와 유사하다. 참고할것(ghost4551.tistory.com/26) 연결 요소 찾기와 유사하게 로직을 작성하되 몇가지만 고려해주면된다. 1. 배추가 위치한 곳은 1이된다. 한번 방문했다면 해당노드를 0의 값으로 만들어준다. (방문처리) 2. 상하좌우 옮겨갈수 있으므로 옮겨주되 그래프의 범위인지 검사 크게 이렇게 두가지만 고려해주면 된다. function solution() { let cnt = 0; //그래프 전체 탐색 for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { //그래프의 값을 돌면서 1이 존..
백준 DFS 알고리즘 11724번_연결 요소의 개수 난이도 : 실버II 문제 설명 입출력 문제 풀이 : 이 문제 또한 전형적인 DFS 문제이다. 또한 문제 제목처럼 연결된 정점들의 묶음의 수를 출력하면된다. 기존에는 한번만 DFS함수를 호출하면 재귀적으로 돌면서 인접 노드들을 알아낼 수 있다. 그렇게 되면 한번의 호출만으로 i(시작노드)와 인접한 모든 노드들은 방문 처리가 된다. 이를 이용하여 반복문을 통해서 graph의 길이만큼 DFS함수를 호출한다. 하지만 처리된 노드들은 방문처리가 되었기 때문에 방문되지않은 노드가 있을때만 DFS함수를 호출하고 연결요소를 카운트 해주면된다. //실버2 연결 요소의 개수 //DFS 기본 로직과 동일 function DFS(v) { visited[v] = true; f..
백준 DFS 알고리즘 1260번_DFS와 BFS 난이도 : 실버II * DFS와 BFS 두개 다 요구하는 문제입니다. 문제 설명 입출력 문제 풀이 : 문제 제목부터 DFS와 BFS를 요구하는 문제이다. 기본 DFS와 BFS 구현 알고리즘을 이용해서 해결하면된다. 인접행렬 방식으로 풀어줘야한다는 것만 알고 풀면된다! //실버2 DFS와 BFS //DFS함수 function DFS(v) { //노드 방문처리 visited[v] = true; //출력을 위해 리스트에 노드 삽입 DFS_graph.push(v); for (let i = 1; i < graph.length; i++) { //graph에 1이 있고 방문하지 않았다면 재귀 호출 if (graph[v][i] === 1 && visited[i] === ..
백준 DFS 알고리즘 2599번_짝 정하기 난이도 : 실버IV 해결하지 못한 문제입니다. 문제 설명 입출력 문제 풀이 : 초등학교 출신을 순서대로 배열의 index값으로 생각하고 이차원 배열에 각각 학교별로 남자, 여자의 수를 입력 받는다. 그후 list(초등학교)를 순서대로 돌면서 자기학교를 제외한 여학생들의 수와 비교해서 쌍을 맺을수 있는대로 맺어준다. 맺은 쌍 만큼 남학생, 여학생 수를 빼주고 맺은 쌍의 수를 배열에 넣어준다. 이 과정을 마치고나면 list(초등학교)에는 맺을 수 있는 쌍을 제외한 값이 존재한다(모두 쌍을 맺었다면 모든 배열에 0 그렇지 않다면 0을 제외한 수가 남게 된다.) 그후 모든 list(초등학교)에 0만 존재한다면 모든 쌍이 맺어진것이므로 학교의 수만큼 짤라서 맺어진 쌍을 ..