Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 오브젝트 풀링
- raycasting
- pccp 기출문제 3번
- 2D슈팅게임
- 너비 우선 탐색
- Ainimation Blending
- 플레이어 방향전환
- 유니티
- Blend Type
- Object Poling
- Lv2
- pccp 기출문제 1번
- Hpbar
- pccp 기출문제 2번
- 플레이어 이동
- CSharp #자료구조
- Algorithm
- ASTAR
- 깊이 우선 탐색
- C#
- 충돌위험 찾기
- Back Tracking
- LayerMark
- Unity
- Animation State Machine
- 프로그래머스
- heap tree
- Hp바
- Scrooling
- Object Pooling
Archives
- Today
- Total
주녘공부일지
[Algorithm C#] BFS, DFS ( + Back Tracking ) 본문
1. BFS(Breadth First Search) - 너비 우선 탐색
최단 경로, 임의의 경로를 찾고 싶을 때, 등에 사용
- 큐(FIFO) 사용
// 큐를 이용
public void BFS(int index)
{
Node root = nodes[index];
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(root);
root.marked = true;
while (queue.Count > 0)
{
var node = queue.Dequeue();
for (int i = 0; i < node.adjacent.Count; i++)
{
var adjacentNode = node.adjacent[i];
if (adjacentNode.marked == false)
{
adjacentNode.marked = true;
queue.Enqueue(adjacentNode);
}
}
Console.Write(node.data + ",");
}
}
2. DFS(Depth First Search) - 깊이 우선 탐색
조합류 최단거리로 갈 수 있는 경로의 수, 목적지 도달 여부, 등에 사용
- 스택(LIFO) 사용, 재귀 함수 사용
// 스택을 이용
public void DFS(int index)
{
Node root = nodes[index]; ;
Stack<Node> stack = new Stack<Node>();
stack.Push(root);
root.marked = true;
while (stack.Count > 0)
{
var node = stack.Pop();
for (int i = 0; i < node.adjacent.Count; i++)
{
var adjacentNode = node.adjacent[i];
if (adjacentNode.marked == false)
{
adjacentNode.marked = true;
stack.Push(adjacentNode);
}
}
Console.Write(node.data + ", ");
}
}
// 재귀함수를 이용
public void DFS_Recursive(int index)
{
DFS_Recursive(nodes[index]);
}
public void DFS_Recursive(Node node)
{
node.marked = true;
Console.Write(node.data + ",");
for (int i = 0; i < node.adjacent.Count; i++)
{
var adjacentNode = node.adjacent[i];
if (adjacentNode.marked == false)
{
dfs_recursive(adjacentNode);
}
}
}
+ Back Tracking ( DFS + 조건 추가 )
DFS 알고리즘에 의해 탐색을 하다가 현재 탐색 중인 노드의 값으로 인해 특정 조건을 만족하지 않게 된다면 해당 노드의 자식 노드들은 더 이상 탐색하지 않고 부모 노드로 돌아가 다음 자식 노드를 탐색하는 것을 말함
즉, 유망한 노드라면 탐색을 이어가고 유망하지 않은 노드라면 탐색하지 않고 다음 자식 노드를 탐색
- Stack에 Push하거나 재귀함수를 호출하기 전에 특정 조건을 만족하는지 여부를 판단해 특정 조건을 만족하
지 않는다면 다시 부모노드로 돌아가 다음 자식노드를 체크하도록 로직을 구성하면 됨
ex) 백 트래킹 예제 ( CodingTest ) // DFS + 백트래킹 조건 체크 메서드
https://godgjwnsgur7.tistory.com/151
'Programming > Algorithm' 카테고리의 다른 글
[Algorithm] A* 알고리즘 (0) | 2024.09.28 |
---|---|
[Algorithm C#] 최소 신장 트리 MST ( 크루스칼, 프림 ) (1) | 2023.10.19 |
[Algorithm C#] 동적 계획법(DP) / Memoization, Tabulation (1) | 2023.10.18 |
[Algorithm C#] 소수 판별 최적화 알고리즘 (제곱근, 에라토스테네스의 체) (0) | 2023.08.25 |