길찾기 알고리즘 DFS,BFS

해당 기능을 찾아보게 된 이유

다음달부터 진행할 사이드 프로젝트에서 사용할 가능성이 높은
길찾기 알고리즘(Pathfinding)에 대해 미리 정리해두는 포스트입니다.
초기 개발 시간 단축을 위해 정리해봤습니다.

 

DFS

Depth_First_Search(깊이 우선 탐색)은

그래프나 트리에서 한방향으로 끝까지 들어갔다가 막히면 되돌아오는 탐색 알고리즘이다.

 

*미로에서 한 방향으로 계속 가다가 막히면 다시 돌아와 다른 길을 찾는 방식

 

*백트래킹<되돌아가기> 개념과 잘 어울리며, 전체 경로 탐색에 적합하다.

 

DFS의 특징

1. 스택 기반의 자료구조

2. 최단 거리 보장이 안된다.

3.퍼즐, 미로 찾기, 조합/순열, 영역 탐색

4. 구현이 간단하여 메모리 사용이 적고 백트래킹에 유리하다

5. 무한루프에 빠질 위험이 있다.

 

using System.Collections.Generic;
using UnityEngine;

public class DFSPathfinder : MonoBehaviour
{
    // 맵 (0 = 길, 1 = 벽)
    int[,] map = {
        { 0, 1, 0, 0, 0 },
        { 0, 1, 0, 1, 0 },
        { 0, 0, 0, 1, 0 },
        { 1, 1, 0, 0, 0 },
        { 0, 0, 0, 1, 0 }
    };

    Vector2Int start = new Vector2Int(0, 0);
    Vector2Int goal = new Vector2Int(4, 4);

    int height, width;
    bool[,] visited;
    List<Vector2Int> path = new List<Vector2Int>();

    void Start()
    {
        height = map.GetLength(0); // 행 (세로)
        width = map.GetLength(1);  // 열 (가로)
        visited = new bool[height, width];

        if (DFS(start))
            PrintPath(path);
        else
            Debug.Log("경로 없음");
    }

    bool DFS(Vector2Int pos)
    {
        int x = pos.x;
        int y = pos.y;
		//범위를 제한하는 조건
        if (x < 0 || x >= width || y < 0 || y >= height)
            return false;
            //막혀있는 벽이거나 방문했단 위치면 false를 반환한ㄷ
        if (map[y, x] == 1 || visited[y, x])
            return false;
		//위에 조건에서 필터링이 안되면 새로 방문하는 지역이다. 이동할 위치에 논리값을 초기화한다.
        visited[y, x] = true;
        //길에 현재 포지션을 추가한다.
        path.Add(pos);
		//만약 포지션이 골 지점이면 true를 반환한다.
        if (pos == goal)
            return true;
		//4방향을 할당한 변수
        Vector2Int[] dirs = {
            new Vector2Int(0, 1),   // 위
            new Vector2Int(0, -1),  // 아래
            new Vector2Int(-1, 0),  // 왼쪽
            new Vector2Int(1, 0)    // 오른쪽
        };
		
        //4방향을 순서대로 체크한다.
        foreach (var dir in dirs)
        {//여기서 재귀적으로 방향을 체크한다. 만약에 골인 지점이면 true를 반환한다.
        //만약에 끝에 길이 없으면 하단의 백트래킹을 진행한다.<도착지 까지의 경로를 지운다>
            if (DFS(pos + dir))
                return true;
        }

        path.RemoveAt(path.Count - 1); // 백트래킹
        return false;
    }

    void PrintPath(List<Vector2Int> result)
    {
        foreach (var p in result)
            Debug.Log($"경로: {p}");
    }
}

BFS

너비 우선 탐색은 시작 노드에서 가까운 노드부터 차례대로 탐색해 나가는 알고리즘이다.

1. 큐에넣고 꺼낸 후 그 다음 레벨을 큐에 넣는 방식

2. 길찾기에서 항상 최단 경로를 보장

3. 경로 최적화

4. 메모리 사용이 많아서 느릴 수 있다.

DFS는 깊게 BFS는 넓게

using System.Collections.Generic;
using UnityEngine;

public class BFSPathfinder : MonoBehaviour
{
    //맵 제작 
    int[,] map = {
        { 0, 1, 0, 0, 0 },
        { 0, 1, 0, 1, 0 },
        { 0, 0, 0, 1, 0 },
        { 1, 1, 0, 0, 0 },
        { 0, 0, 0, 1, 0 }
    };
	//시작지점 
    Vector2Int start = new Vector2Int(0, 0);
    //도착 지점 
    Vector2Int goal = new Vector2Int(4, 4);

    int height, width;
    bool[,] visited;
    Vector2Int[,] parent;

    void Start()
    {
        height = map.GetLength(0);
        width = map.GetLength(1);

        visited = new bool[height, width];
        parent = new Vector2Int[height, width];

        RunBFS();
    }

    void RunBFS()
    {
        Queue<Vector2Int> queue = new Queue<Vector2Int>();
        queue.Enqueue(start);
        visited[start.y, start.x] = true;

        Vector2Int[] dirs = {
            new Vector2Int(0, 1),
            new Vector2Int(0, -1),
            new Vector2Int(-1, 0),
            new Vector2Int(1, 0)
        };

        bool found = false;

        while (queue.Count > 0)
        {
          //현재 포지션 할당 
            Vector2Int current = queue.Dequeue();
			//현재 포지션이 골지점이랑 같다면?
            if (current == goal)
            {
                found = true;
                break;
            }

            foreach (var dir in dirs)
            {
                Vector2Int next = current + dir;
                int x = next.x;
                int y = next.y;

                if (x < 0 || x >= width || y < 0 || y >= height)
                    continue;
                if (map[y, x] == 1 || visited[y, x])
                    continue;

                visited[y, x] = true;
                parent[y, x] = current;
                queue.Enqueue(next);
            }
        }

        if (found)
        {
            List<Vector2Int> path = new List<Vector2Int>();
            Vector2Int current = goal;

            while (current != start)
            {
                path.Add(current);
                current = parent[current.y, current.x];
            }
            path.Add(start);
            path.Reverse();

            foreach (var p in path)
                Debug.Log("BFS 경로: " + p);
        }
        else
        {
            Debug.Log("경로 없음 (BFS)");
        }
    }
}

 

 

즉 DFS는 한 방향으로 갔다가 길을 못찾으면 되돌아오고

BFS는 모든 방향으로 가지처럼 넓게 나아가 최소 거리를 탐색한다는 것!