Two ways to implement DFS. (Recursive or Stack)

https://youtu.be/CUTXL4NFTGE

이 영상이 가장 빠르고 효과적이게 DFS, BFS의 구현 방법의 종류와 동작 과정을 설명하신것 같다.

 

DFS를 구현할 때 습관적으로 재귀를 사용해왔는데 정확도가 너무 떨어졌다.

생각이 너무 복잡해짐 (종료조건, return 값, return 후에 처리해줘야 하는 값들 등등 머리가 너무 아픔)

체크해야 할것이 많다는 것은 그만큼 실수할 확률이 늘어난다는 의미와 같다. 그래서 이제 stack으로 DFS를 구현해보고자 한다. (stack도 별반 다를바 없으면 어카지 ㅋㅋ)

 

예시 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43164#

프로그래머스

 

In Recursive

def solution(tickets):
    answer = ["ICN"]
    def defaultRoute():
        dic = {}
        for ticket in tickets:
            start, end = ticket
            if start in dic:
                dic[start].append(end)
            else:
                dic[start]=[end]
        for k,v in dic.items():
            v.sort()
        return dic
    
    def dfs(depart,route,tAnswer):
        tempAnswer = tAnswer[:]
        if depart not in route or len(route[depart]) == 0:
            for k,v in route.items():
                if len(v) != 0:
                    return False
            tempAnswer.append(depart)
            return tempAnswer
        
        tempAnswer.append(depart)
        arrives = route[depart]
        for i in range(len(arrives)):
            arrive = arrives[i]
            arrives.pop(i)
            check = dfs(arrive,route,tempAnswer)
            if check:
                return check
            else:
                arrives.insert(i,arrive)
                
        
    route = defaultRoute()
    answer = dfs("ICN",route,[])
    return answer

깔끔하게 잘 짠 코드라고 보여지지 않을 수 있지만, 열심히 리팩토링 한거다...

재귀함수 짜며 고민해야 할것은

1. 종료조건

2. 종료 후 return

3. 값 추가 시점

4. 재귀함수 호출 시점

5. 재귀함수 return 후 처리 과정 (추가 한 값 다시 빼기 or 계속 return)

등등.. 이 있다.

 

졸라 귀찮다!

 

이것을 stack으로 바꿔서 한번 구현해보면.

def solution(tickets):
    path = []

    # 1. {시작점: [도착점리스트]} 형태로 그래프 생성
    graph = defaultdict(list)
    for (start, end) in tickets:
        graph[start].append(end)

    # 2. 도착점 리스트를 역순 정렬
    for airport in graph.keys():
        graph[airport].sort(reverse=True)

    # 3. 출발지는 항상 ICN이므로 stack에 먼저 넣어두기
    stack = ["ICN"]
    # 4. DFS로 모든 노드 순회
    while stack:
        # 4-1. 스택에서 가장 위의 저장된 데이터 꺼내오기
        top = stack.pop()

        # 4-2. top이 그래프에 없거나, top을 시작점으로 하는 티켓이 없는 경우 path에 저장
        if top not in graph or not graph[top]:
            path.append(top)
        # 4-3. top을 다시 스택에 넣고 top의 도착점 중 가장 마지막 지점을 꺼내와 스택에 저장
        else:
            stack.append(top)
            stack.append(graph[top].pop())

    # 5. path를 뒤집어서 반환
    return path[::-1]

이렇게 된다고 한다.

직접 구현해보진 못했다. 왜냐면 재귀로 짰을대의 종료조건이 저 코드에 없어도 잘 돌아가는것이 이해가 안갔기 때문이다.

 

즉, 결론은. 내가 문제 이해를 잘 못해서 어려웠던 것이다!! (문제가 이상하게 테스트 케이스 짜기가 어려워서 내가 원하는 상황을 못만듦)

=> stack으로 짜나 재귀로 짜나 생각해야 할것은 똑같이 여러개임.