BFS(너비 우선 탐색), DFS(깊이 우선 탐색) 정의하기
너비 우선 탐색(BFS)이란 : 루트 노드를 시작으로 인접한 노드부터 차례로 탐색하는 방법
- 시작 정점으로부터 가장 가까운 노드를 시작으로 순차적으로 검색하는 방법.
- 왼쪽부터 차례로 탐색한다.
깊이 우선 탐색(DFS)이란 : 루트 노드를 시작으로 다음 가지로 넘어가기 전에 해당 분기를 전부 탐색하는 방법.
- 만약, 어느 한 분기의 깊이가 무한하면 다음 분기로 넘어갈 방법이 없기때문에 깊이를 제한한다.
- 깊이 제한에 도달하였는데도 목표 노드가 발견되지 않으면 해당 노드의 부모 노드로 되돌아 오는데, 이를 백 트래킹(BackTracking) 이라 한다.
경로 탐색 구현작업 세팅하기
작업은 Unity C# 으로 진행하였습니다.
먼저, 경로 탐색을 본격적으로 구현하기 이전에 세팅을 해보겠습니다.
public class Node
{
public int value; // value 에 따라 벽인지 시작점인지 도착점인지 구분 가능
public bool isVisit; // 이미 방문한 노드인지 확인하기 위한 변수
public Node(int value, bool isVisit = false)
{
this.value = value;
this.isVisit = isVisit;
}
}public class GameManager : MonoBehaviour
{
int[,] graph; // 2차원 배열
Node[,] nodes; // isVisit 변수를 포함하는 Node 클래스를 graph 의 크기에 같게 할당
const int start = 2; // 시작 지점
const int goal = 3; // 도착 지점
Dictionary<int, Color> colorDic;
void Start()
{
colorDic = new Dictionary<int, Color>();
// 2차원 배열 초기화하기
graph = new int[10, 10]
{
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,2,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,3,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
nodes = new Node[10,10];
for(int y = 0; y < 10; y++)
{
for(int x = 0; x < 10; x++)
{
nodes[y, x] = new Node(graph[y, x]);
}
}
colorDic.Add(0, Color.white);
colorDic.Add(1, Color.black);
colorDic.Add(start, Color.blue);
colorDic.Add(goal, Color.red);
}
private void OnDrawGizmos()
{
// OnDrawGizmos 가 실행하기 전에도 실행되므로 예외처리 먼저
if (nodes == null) return;
for (int y = 0; y < nodes.GetLength(0); y++) // array.GetLength(Dimension) // 해당 차원 배열 길이
{
for (int x = 0; x < nodes.GetLength(1); x++)
{
Vector3 offset = new Vector3(x*2, y*2, 0); // 기즈모 백개 퍼뜨리기, 2를 곱한이유: 반지름 1짜리 구체 그릴거니까
Gizmos.color = colorDic[nodes[y,x].value];
Gizmos.DrawSphere(transform.position - offset, 1);
}
}
}
}
이렇게 먼저 세팅을 해두면 실행시 이런 화면이 나타납니다.
너비 우선 탐색(BFS) 경로 탐색
시작 지점(파란색) 에서 도착 지점(빨간색) 까지 가기위해 BFS 알고리즘을 기반으로 탐색한다면 어떤식으로 탐색이 진행될지 생각해봅시다.
BFS 는 가장 인접한 노드부터 순차적으로 접근합니다.
그렇다면 시작 지점에서 가장 인접한 노드는 상,하,좌,우 총 4개의 노드가 되겠네요. 그림으로 표현하면 다음과 같이 될것입니다.
트리 구조로 치면 시작 지점이 루트 노드인 셈이고 1,2,3,4 번 노드가 각각 루트 노드의 자식 노드인 셈입니다. 그리고 그 자식노드들은 또 상,하,좌,우 4개의 자식노드가 존재하는 구조라 볼 수 있습니다.
여기서 너비 우선 탐색은 저 자식노드를 하나하나 순차적으로 탐색합니다. 그렇다면 1,2,3,4 순이 되겠네요.
만약 1을 탐색했는데 목표지점이 아니라면 1의 자식노드들 중 방문하지 않은 노드도 탐색 경로에 포함 시켜주어야합니다.
그렇지만 너비 우선 탐색에서 1의 자식노드 보다 더 우선시 되는것은 루트 노드의 인접 노드인 2,3,4 번 노드가 될 것입니다.
여기서 우리는 각 노드의 자식노드를 관리해줄 컬렉션의 필요성을 느낄 수 있습니다. 자식 노드들을 컬렉션에 담고 하나씩 전부 탐색할테니까요.
어떠한 노드를 탐색했을 때 목표 노드가 아니라면 그 노드의 자식 노드들 중 방문하지 않은 노드를 컬렉션에 담아주면 되는겁니다.
그럼 자식 노드들을 어떤 컬렉션에 담는 것이 좋을지 생각해보아야합니다.
만약, 1을 탐색했을때의 결과입니다.
1을 탐색했는데 목표지점이 아니군요. 1의 자식노드 중 방문한 노드(루트노드)를 제외한 나머지 자식노드를 탐색할 준비를 합니다. 하지만 아직 루트노드의 모든 자식노드를 탐색하지 않았으므로 다음 레벨인 1의 자식노드는 탐색을 미룹니다.
쉽게말해, 자식노드로 등록된 번호 순서대로 탐색이 진행됩니다!
넣은 순서대로.. 선입 선출의 방식이니 큐를 사용하여 구현하면 되겠습니다.
public class GameManager : MonoBehaviour
{
int[,] graph; // 2차원 배열
Node[,] nodes;
const int start = 2;
const int goal = 3;
// 너비 우선 탐색을 하기위한 큐
Queue<Vector2> queue;
Dictionary<int, Color> colorDic;
public float speed;
void Start()
{
colorDic = new Dictionary<int, Color>();
queue = new Queue<Vector2>();
graph = new int[10, 10]
{
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,2,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,3,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
nodes = new Node[10,10];
for(int y = 0; y < 10; y++)
{
for(int x = 0; x < 10; x++)
{
nodes[y, x] = new Node(graph[y, x]);
}
}
Visit(3, 3); // 루트 노드부터 방문
colorDic.Add(0, Color.white);
colorDic.Add(1, Color.black);
colorDic.Add(start, Color.blue);
colorDic.Add(goal, Color.red);
colorDic.Add(99,Color.green);
StartCoroutine(FindGoalCo());
}
IEnumerator FindGoalCo()
{
int y = 3; // 시작 부분 Y
int x = 3; // 시작 부분 X
bool isFind = false;
while(isFind == false)
{
if(TryVisit(y,x,ref isFind)) // 방문 성공
{
yield return new WaitForSeconds(speed);
}
else // 방문 실패
{
Pop(out y, out x); // 큐 내의 자식 노드 좌표로 이동
}
yield return null;
}
}
void Pop(out int y, out int x)
{
Vector2 temp = queue.Dequeue();
x = (int)temp.x;
y = (int)temp.y;
}
bool TryVisit(int curY, int curX, ref bool isFind)
{
// 다음 조건들은 방문 실패로 처리
if (curY >= 10 || curY <= 0 || curX >= 10 || curX <= 0) // 좌표 범위를 벗어났다면
return false;
if (nodes[curY, curX].isVisit) // 이미 방문 했다면
return false;
if (nodes[curY, curX].value == 1) // 벽이라면
return false;
if(isCheckGoal(curY,curX))
{
Debug.Log("목적지 찾았음");
isFind = true;
return false;
}
Visit(curY, curX);
return true;
}
public void Visit(int curY, int curX) // 방문할 때 마다 해당 노드의 자식노드 큐에 추가
{
nodes[curY, curX].isVisit = true;
nodes[curY, curX].value = 99;
queue.Enqueue(new Vector2(curX - 1, curY));// 왼쪽 자식노드
queue.Enqueue(new Vector2(curX, curY + 1)); // 위쪽 자식노드
queue.Enqueue(new Vector2(curX + 1, curY)); // 오른쪽 자식노드
queue.Enqueue(new Vector2(curX, curY - 1)); // 아래쪽 자식노드
}
bool isCheckGoal(int curY, int curX) // 목표 노드인지 확인하는 메서드
{
return nodes[curY, curX].value == goal;
}
private void OnDrawGizmos()
{
// OnDrawGizmos 가 실행하기 전에도 실행되므로 예외처리 먼저
if (nodes == null) return;
for (int y = 0; y < nodes.GetLength(0); y++) // array.GetLength(Dimension) // 해당 차원 배열 길이
{
for (int x = 0; x < nodes.GetLength(1); x++)
{
Vector3 offset = new Vector3(x*2, y*2, 0); // 기즈모 백개 퍼뜨리기, 2를 곱한이유: 반지름 1짜리 구체 그릴거니까
Gizmos.color = colorDic[nodes[y,x].value];
Gizmos.DrawSphere(transform.position - offset, 1);
}
}
}
}
위 코드에서 눈여겨 볼 메서드는
Visit() 메서드, TryVisit() 메서드, Pop() 메서드 입니다.
TryVisit() 메서드에서 방문할 수 있는 노드인지 검사를 해주고 Visit() 메서드를 실행시켜줍니다.
Pop 메서드는 방문에 실패했을 때 큐에서 해당 노드를 Dequeue 해준 뒤 다음 자식 노드로 좌표를 이동시켜줍니다.
깊이 우선 탐색(DFS) 경로 탐색
이번엔 깊이 우선 탐색을 활용하여 경로를 탐색해보겠습니다.
깊이 우선 탐색은 해당 가지를 전부 탐색하고 나서 백트래킹을 합니다.
같은 상황이 주어져있다고 해봅시다.
시작 지점의 노드의 자식노드로 1,2,3,4 번 노드가 있습니다. 여기서 4번 먼저 탐색을 하게되면 다음과 같이 될 것입니다.
이후에는 깊이 우선 탐색이므로 4번 노드의 자식노드중 7번노드를 검색할 것입니다.
이는 나중에 들어간 노드부터 검사하는 방식으로 자식 노드들을 큐가 아닌 스택에 담아 관리하면 될 것입니다.
사실, 위 코드에서 queue 부분을 전부 stack 으로 바꿔주기만 하면 깊이 우선 탐색으로 전환됩니다. 그렇기에 따로 코드를 적어두진 않겠습니다.
'알고리즘' 카테고리의 다른 글
| 알고리즘 < 버블 정렬(Bubble Sort)> (2) | 2024.03.14 |
|---|---|
| 알고리즘 <이진 탐색 알고리즘 시간 복잡도 계산하기> (0) | 2024.02.17 |
