본문 바로가기

728x90

BFS2

[Softeer] Lv3. GINI야 도와줘 (Java) 1. 문제 문제 링크 : Lv3. GINI야 도와줘 주제 : BFS 2. 풀이 과정 및 정리 예전에 비슷한 문제를 풀었던 기억이 나서 또 비슷하게 풀었다. (문제 풀이 기록 - 3055번 탈출) https://soo-note.tistory.com/52 [TIL] Algorithm - 다익스트라 + 그래프 문제 풀이(BFS) 1. 다익스트라 알고리즘(Dijkstra algorithm) 모든 간선에 대한 가중치가 항상 0이상임을 가정하고 두 꼭짓점 간의 가장 짧을 경로를 찾는 알고리즘 간선 완화(Edge Relaxation) 시작 정점 s에서 다른 정점 v soo-note.tistory.com 저번에는 파이썬으로 풀었는데 이번에 자바로 풀어보았다. 이번에도 핵심은 비오는 시간을 구하고 이에 따른 이동방법을 .. 2024. 2. 22.

[graph] 너비 우선 탐색(BFS, Breadth First Search) 너비 우선 탐색(BFS, Breadth First Search) 시작 정점으로부터 인접한 정점들을 모두 차례로 방문한 후 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례로 방문하는 방법 가까운 정점들을 먼저 방문하고 멀리 있는 정점들은 나중에 방문하는 순회 방법 인접한 정점들에 대해 차례로 다시 너비 우선 탐색을 반복해야 하므로 선입선출(First-IN First-Out) 구조인 큐(Queue) 사용 BFS 수행순서 큐가 공백이 될 때까지 빨간 상자 부분을 반복한다. BFS 과정 표현 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ Queue가 비었으므로 탐색 종료 결과 : 1 → 2 → 4 → 3 → 5 인접 행렬로 구현한 그래프 BFS static void BFS(int[][] graph, int v) { /.. 2023. 3. 7.

이전 1 다음

728x90

티스토리툴바