[C#] 깊이 우선 탐색 (DFS) 개발 적용 사례 - 폴더구조 찾기

폴더 형태의 구조를 담은 DB 또는 그러한 형태를 반환하는 API를 경험할 일이 많아졌다.

 

[상위폴더 여부 | 상위 폴더 Id | 폴더 Id | 폴더 이름]

 

간추려 위와 같은 컬럼이 있는 DB가 있거나,

유사형태의 값을 반환하는 API를 만났다.

 

DB만 있었다면 DB에서 recurrsive 테이블로 재귀로 뽑아 내는 것도 방법이겠지만

API를 사용해야만 하는 시점에서는 위 형태의 반환 값을 폴더구조로 풀어내는 것에 대한 고민이 있었다.

 

(공부 뒤 블로그나 github에 올리지 못한 내용이 더 많아서 공부를 뜨문뜨문한다고 보실 분들도 있겠지만...

필자는 계속 책을 구매하거나 인강을 듣거나 아주 작은 단위의 프로젝트를 혼자 진행하며

공부하고 찾아보면서 학습중이었다는 점....)

 

 

그러다 DFS를 여기 적용할 수 있겠다는 생각이 들었다.

이 포스트에서는 그러한 예제를 풀어가려한다.

 

 

재직회사에서 C#을 쓰고 있어 C#으로 개발하였으니 다른언어를 하셨더라도 원리로 가져가면 될 것 같다.

 

 

특히,

폴더명으로 검색하기에는

a \ b

a \ c \ b 

의 경우 처럼 이름은 같지만 다른 위치에 있는 것을 프로그램은 구분해서 조회할 수 없기 때문에 폴더구조로 뽑아오거나 id를 뽑아오는 것은 매우 필연적이기 떄문에 이 작업이 필요할때가 많다.

 

 

먼저 아래와 같은 클래스를 작성했다.

DB에서 4개 컬럼을 읽어다 넣었거나, API 반환값이거나, 혹은 읽거나 받은 정보를 여기에 담았다고 가정하자.

class Folder
{
    public int ParentId { get; set; }
    public int Id { get; set; }
    public bool HasParent { get; set; }
    public string Name { get; set; }
    
    public string NameHierarchy { get; set; }
    public string IdHierarchy { get; set; }
}

 

 

Folder 클래스의 인스턴스에 HasParent, ParentId, Id, Name이 기입 되어있는 List가 있다고 가정하자.

(NameHierarchy, IdHierarchy는 폴더구조를 \ 구분자로 만들 필드로 처음엔 빈칸으로 시작한다고 가정한다.)

List<Folder> wholeFolders = new List<Folder>();

 

 

DFS 알고리즘을 적용하기 위해 시작 노드를 정리할 필요가 있다.

다만, 폴더구조를 로그를 찍었을때 직관적으로 더 잘 보이게 하기위해 visited는 생성하지 않는다.

 

HasParent 같은 친절한 필드 또는 컬럼이 없는 경우가 있겠지만 그런경우에는 parent id가 null이거나 0 등 특별히 최상위 폴더를 알 수 있는 조건이 있을 것이다. 여기서는 HasParent가 true가 아니면 최상위 폴더이다.

List<Folder> rootfolders = wholeFolders.Where(f => !f.HasParent)
				.ToList();

 

 

위에서 filtering한  인스턴스들을 Stack을 선언하여 노드로 push한다.

최상위 폴더는 폴더이름, 폴더 id 자체가 폴더구조 이므로 이 값을 Hierarchy류 필드에 넣는다.

Stack<Folder> stack = new Stack<Folder>();
foreach (var rootfolder in rootfolders)
{             
    rootfolder.IdHierarchy = rootfolder.Id.ToString();
    rootfolder.NameHierarchy = rootfolder.Name;
    stack.Push(rootfolder);
}

 

 

이제 루프를 돌린다.

첫 번째 순회에서는 root folder들을 stack에 쌓았으므로

가장 마지막 node를 pop하여, 전체 폴더 중에서 parent id가 root folder의 id와 동일한 폴더들을 찾아 리스트로 반환하게 된다.

그렇게 조회한 하위 폴더를 상위폴더\현재폴더 값으로 Hierarchy류에 입력하고 stack에 push한다.

다음루프에서는 방금 중 가장마지막에 push한 폴더를 꺼내 다시 한번 절차를 거치게 된다.

이렇게. 최상위폴더에서 최하위 폴더까지 순회 후 다음 노드로 넘어가게 된다.

Folder folder = new Folder();
while (stack.Count > 0)
{
    folder = stack.Pop();               
    foreach (var child in wholeFolders.Where(f => f.ParentId == folder.Id))
    {
        child.NameHierarchy = $@"{folder.NameHierarchy}\{child.Name}";
        child.IdHierarchy = $@"{folder.IdHierarchy}\{child.Id}";
        stack.Push(child);
    }
}

 

한번에 작성해보면

List<Folder> wholeFolders = new List<Folder>(); // 무언가 조회된 것이라 가정한다.

Stack<Folder> stack = new Stack<Folder>();
foreach (var rootfolder in wholeFolders.Where(f => !f.HasParent)) // 1회 순회 - IEnumerable사용
{             
    rootfolder.IdHierarchy = rootfolder.Id.ToString();
    rootfolder.NameHierarchy = rootfolder.Name;
    stack.Push(rootfolder);
}


Folder folder = new Folder();
while (stack.Count > 0)
{
    folder = stack.Pop();               
    foreach (var child in wholeFolders.Where(f => f.ParentId == folder.Id))  // 1회 순회 - IEnumerable사용
    {
        child.NameHierarchy = $@"{folder.NameHierarchy}\{child.Name}";
        child.IdHierarchy = $@"{folder.IdHierarchy}\{child.Id}";
        stack.Push(child);
    }
}


class Folder
{
    public int ParentId { get; set; }
    public int Id { get; set; }
    public bool HasParent { get; set; }
    public string Name { get; set; }
    
    public string NameHierarchy { get; set; }
    public string IdHierarchy { get; set; }
}

 

DFS를 폴더구조화에 적용한 예제였다. DFS가 나같은 비전공자에게는 한번에 와닿지 않으나, DFS의 개념을 이해는 못한체 외우고만 있다가 필요할때 써보려고하니 어떤 로직으로 어떻게 적용되는지 이해가 되어 기뻤던 개발이었다.