DFS - 깊이 우선 탐색 (C#으로 길 찾기 구현)

 

- Depth First Search의 약자

- 현재 정점(노드)에서 간선으로 연결된 정점중 가장 깊은 정점까지 탐색하고

목표 정점이 없으면 이전 정점으로 돌아가 간선으로 연결된 다른 정점으로 또다시 탐색한다.

- 위 방법을 반복하면서 정점들을 순회하게 된다.

- DFS와 대조되는 BFS (너비 우선 탐색)도 있다.

- 일반적으로 재귀호출로 구현하는 방법과 스택으로 구현하는 방법이 있다.

 

DFS 깊이 우선 탐색의 탐색 순서

BFS 너비 우선 탐색의 탐색 순서

 

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        MapController mapController = new MapController();
        // 길 체크 플래그를 초기화해준다.
        mapController.ClearCheckRoad();

        // 시작 좌표와 목적지 좌표를 매개변수로 넘겨준다.
        mapController.DFS(0, 0, 5, 3, null);
        mapController.Log();
    }
}

public class MapController
{
    // 탐색할 맵이다.
    public int[,] maps = new int[,]
    {
        {0, 0, 0, 0, 0, 0 },
        {0, 0, 1, 0, 0, 0 },
        {0, 0, 1, 0, 0, 0 },
        {0, 0, 1, 0, 0, 0 },
        {0, 0, 1, 0, 0, 0 },
        {0, 0, 0, 0, 0, 0 }
        // 목표지점이 5,3인 경우
        // [5,3]->[5,2]->[5,1]->[5,0]->[4,0]->[3,0]->[2,0]->[1,0] 순으로
        
        //{0, 1, 1, 1, 1, 1 },
        //{0, 1, 0, 0, 0, 1 },
        //{0, 1, 0, 1, 0, 1 },
        //{0, 1, 0, 0, 0, 0 },
        //{0, 1, 1, 0, 1, 0 },
        //{0, 0, 0, 0, 1, 0 }
        // 목표지점이 5,5인 경우
        // [5,5]->[4,5]->[3,5]->[3,4]->[3,3]->[4,3]->
        // [5,3]->[5,2]->[5,1]->[5,0]->[4,0]->[3,0]->[2,0]->[1,0] 순으로

    };

    // 상 하 좌 우 방향을 나타낸다.
    public int[,] direction = new int[,]
    {
        { -1,  0 },
        {  1,  0 },
        {  0, -1 },
        {  0,  1 },
    };

    // 한번 들른 길인지 체크한다.
    public bool[,] checkRoad = null;

    private BFSNode bestNode = null;

    public void Log()
    {
        while (bestNode.PrevCount > 0)
        {
            Console.WriteLine(string.Format("[{0},{1}]", bestNode.Y, bestNode.X));

            // bestNode를 순회하며 해당 좌표를 콘솔로 찍어준다.

            // [5,3]->[5,2]->[5,1]->[5,0]->[4,0]->[3,0]->[2,0]->[1,0] 순으로
            bestNode = bestNode.PrevNode;
        }
    }

    public void DFS(int y, int x, int targetY, int targetX, DFSNode prevNode)
    {
        DFSNode node = new DFSNode(y, x, prevNode);
        // 현재 노드가 목표 지점일 경우
        if (node.Y == targetY && node.X == targetX)
        {
            // 가장 빠른길이 아직 없거나
            // 현재 노드가 가장 빠른길일 경우 bestNode에 담는다.
            // 이후 여기에 들어오는 Node들과 bestNode를 비교하여 가장 빠른 길을 담는다.
            if (bestNode == null || (bestNode.PrevCount > node.PrevCount))
                bestNode = node;

            return;
        }

        // 이 좌표는 한 번 들른 길로 체크한다
        checkRoad[y, x] = true;

        // 상 하 좌 우를 체크한다.
        for (int i = 0; i < direction.GetLength(0); i++)
        {
            // 현재 노드의 위치 + (상or하or좌or우)
            int dy = node.Y + direction[i, 0];
            int dx = node.X + direction[i, 1];

            if (CheckMapRange(dy, dx) && CheckMapWay(dy, dx) && !checkRoad[dy, dx])
                DFS(dy, dx, targetY, targetX, node);
        }

        // 재귀로 순환하는 구조이기 때문에
        // 이 좌표를 다시 안가본 길로 바꿔준다.
        checkRoad[y, x] = false;
    }

    private bool CheckMapRange(int y, int x)
    {
        return (y >= 0 && y < maps.GetLength(0) &&
            (x >= 0 && x < maps.GetLength(1)));
    }

    private bool CheckMapWay(int y, int x)
    {
        return maps[y, x] == 0;
    }

    public void ClearCheckRoad()
    {
        checkRoad = new bool[maps.GetLength(0), maps.GetLength(1)];
        for (int i = 0; i < checkRoad.GetLength(0); ++i)
        {
            for (int j = 0; j < checkRoad.GetLength(1); ++j)
                checkRoad[i, j] = false;
        }
    }
}

public class DFSNode
{
    public int X { get; private set; }
    public int Y { get; private set; }
    public DFSNode PrevNode { get; private set; }
    public int PrevCount { get; private set; }

    public DFSNode(int y, int x, DFSNode prevNode)
    {
        Y = y;
        X = x;
        PrevNode = prevNode;

        if (PrevNode == null)
        {
            // 이전 노드가 없으면 시작지점이기 때문에 Count는 0이다.
            PrevCount = 0;
        }
        else
        {
            // 이전 노드가 있다면 이전노드의 '이전노드 갯수' + 1을 해준다.
            // 목표지점에 해당하는 노드는 최종적으로
            // 시작지점에서 목표지점까지의 노드 수가 담기게 된다.
            PrevCount = PrevNode.PrevCount + 1;
        }
    }
}

 

BFS - 너비 우선 탐색 (C#으로 길 찾기 구현)

다람쥐와 포동포동이

 

 

RememberCook 9월 28일 정식 출시!