7/2 탐색 알고리즘 - BFS, DFS, 다익스트라
본문 로딩 중...
댓글 0
댓글을 작성하려면 로그인이 필요합니다.
아직 댓글이 없습니다. 첫 번째 댓글을 작성해보세요.
댓글을 작성하려면 로그인이 필요합니다.
아직 댓글이 없습니다. 첫 번째 댓글을 작성해보세요.
| 용어 | 뜻 | 예시/활용 |
|---|---|---|
| 노드 | 그래프에서 하나의 위치나 상태 | 맵 칸, 도시, 퀘스트 상태 |
| 간선 | 노드와 노드를 연결하는 관계 | 길, 이동 가능 방향 |
| BFS | 가까운 곳부터 넓게 탐색하는 방식 | 최단 칸 수, 전파 범위 |
| DFS | 한 방향으로 깊게 들어갔다 돌아오는 방식 | 백트래킹, 경로 존재 |
| 다익스트라 | 가중치가 있는 그래프의 최단 비용 탐색 | 지형 비용이 다른 길찾기 |
DFS / BFS
다익스트라
다익스트라 알고리즘은 ++음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드++에서 각 모든 노드까지의 최단거리를 구하는 알고리즘을 말한다.
다익스트라 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만,
더 일반적인 변형은 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것으로도 사용한다.
다익스트라 알고리즘은 그리디 알고리즘이자 다이나믹 프로그래밍 기법을 사용한 알고리즘이라고 볼 수 있다.
| 구분 | 그리디 알고리즘 | 다익스트라 알고리즘 |
|---|---|---|
| 의미 | 알고리즘을 설계하는 방식 | 최단 경로를 구하는 구체적인 알고리즘 |
| 핵심 | 현재 가장 좋은 선택을 반복 | 현재 거리가 가장 짧은 정점을 선택 |
| 목적 | 문제에 따라 다름 | 시작점에서 각 정점까지의 최단 거리 계산 |
| 최적해 보장 | 문제의 조건에 따라 다름 | 음수 가중치가 없으면 보장 |
| 관계 | 상위 개념 | 그리디 방식을 사용하는 알고리즘 |
Develog는 단순히 글을 쓰는 공간이 아닙니다. 성장의 과정을 기록하고, 그 기록으로 나를 증명하며 원하는 기회를 얻는 곳이길 바랐습니다. 누군가의 꿈으로 향하는 중간다리가 되는 것, 그것이 Develog를 만든 이유입니다.
우리들의 게임 발매 이야기
안녕하세요. 플밍 4기 입니다. 게임 개발을 배우기 전 네트워크 엔지니어 도메인에서 익히고 배웠던 네트워크 이론에 대한 기초 입니다. 학습에 도움이 되길 바라며 공유 드립니다.
Develog는 단순히 글을 쓰는 공간이 아닙니다. 성장의 과정을 기록하고, 그 기록으로 나를 증명하며 원하는 기회를 얻는 곳이길 바랐습니다. 누군가의 꿈으로 향하는 중간다리가 되는 것, 그것이 Develog를 만든 이유입니다.
안녕하세요. 플밍 4기 입니다. 게임 개발을 배우기 전 네트워크 엔지니어 도메인에서 익히고 배웠던 네트워크 이론에 대한 기초 입니다. 학습에 도움이 되길 바라며 공유 드립니다.
