| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
- 코딩테스트
- frontend
- js
- Git
- 해시
- 혼자 공부해서 개발까지
- DFS
- react
- 그리디
- 팀프로젝트
- 알고리즘 기초
- html
- HTML기초
- 코딩
- c언어
- 그래프
- Mini-React
- 개발자
- 정렬
- 정글
- BFS
- 알고리즘
- 프론트엔드
- Python
- 크래프톤 정글
- 백준
- CSS
- 프론트앤드
- javascript
- 프로그래머스
- Today
- Total
목록BFS (2)
민혁이의 IT스토리
https://www.acmicpc.net/problem/2178 문제 풀이 전략 BFS(Breadth-First Search) 활용: 최단 경로 문제에서는 현재 위치에서 가까운 곳부터 탐색하는 BFS가 적합합니다. DFS는 경로가 존재함을 확인하기엔 좋으나, 최단 거리를 보장하기 위해 별도의 처리가 필요하기 때문입니다.방문 처리와 거리 계산의 통합: 별도의 방문 리스트(visited)를 만들 수도 있지만, 입력받은 미로 리스트 자체에 지금까지 이동한 거리(Step)를 직접 갱신하면 메모리를 아끼고 방문 여부도 동시에 체크할 수 있습니다. 해결 과정데이터 입력: 미로를 2차원 리스트로 입력받습니다. (이때 숫자가 붙어서 들어오므로 list(input())을 활용해 하나씩 쪼개줍니다.)Queue 초기화:..
BFS란?그래프 탐색 알고리즘 중 하나로, 시작 정점에서 가까운 노드부터 차례대로 탐색해 나가는 방식입니다.즉, "넓게 퍼져나가듯" 탐색한다고 해서 너비 우선 탐색이라고 부릅니다. 동작 원리시작 노드를 큐(Queue)에 넣는다.큐에서 노드를 꺼내서 방문한다.방문한 노드의 인접한 노드들을 모두 큐에 넣는다.큐가 빌 때까지 2~3 과정을 반복한다. BFS의 특징 큐(Queue) 사용: FIFO 구조로 탐색 순서를 보장가까운 노드부터 탐색: 레벨별 탐색이 가능최단 경로 탐색에 유리: 가중치가 없는 그래프에서 최단 거리를 찾을 때 많이 사용 마무리BFS는 그래프나 트리에서 가장 기본적인 탐색 알고리즘으로,큐를 활용해 가까운 노드부터 차례대로 탐색하는 방식입니다.특히 최단 거리 문제에서 매우 유용하게 사용되므로 ..