DFS/BFS 완전 정복하기 - 트리구조를 탐색하는 방법

1. 문제

 

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

코딩테스트 연습 - 여행경로

 

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 

 

항상 "ICN" 공항에서 출발합니다

 

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return하도록 solution함수를 완성하세요

 

2. 제한사항

 

모든 공항은 알파벳 대문자 3글자

 

주어진 공항 수는 3개 이상 10000개 이하

 

tickets의 각 행 [a,b]는 a공항에서 b공항으로 가는 항공권이 있다는 의미

 

주어진 항공권은 모두 사용해야함

 

만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return

 

모든 도시를 방문할 수 없는 경우는 주어지지 않는다

 

3. 예시

 

 

4. 나의 풀이

 

일반적인 직선형 탐색은 누구나 할 수 있지만 트리 구조를 탐색하는 것은 쉽지 않다

 

시작 항공을 ICN으로 설정하고 모든 티켓을 전부 사용한 경로를 만들어야하므로

 

2번째 예제를 예로 들어 생각해보면 우리가 탐색해야할 구조는...

 

 

위와 같은 방식으로 탐색해야할것

 

 

def solution(tickets):
    
    from collections import deque
    from copy import deepcopy
    
    deque_ticket = deque(tickets)
    
    dir_list = deque()

    for a,b in tickets:

        if a == 'ICN':
            
            copy_ticket = deepcopy(tickets)

            copy_ticket.remove([a,b])

            dir_list.append([[a,b],deque(copy_ticket)])

 

pop하는데 시간을 줄이기 위해 deque를 사용하고 원본을 변경시키지 않기위해 deepcopy를 사용했다

 

먼저 출발공항이 반드시 ICN인 여행경로를 만들어야하므로 tickets에서 하나씩 순회를 해서 ICN인 ticket들을 찾는다

 

출발공항이 ICN이라면 우리의 여행경로 첫번째이므로

 

현재 순회하고 있는 tickets의 deepcopy를 구하고

 

현재 순회하고 있는 [a,b]는 탐색이 끝났으니까 현재 만든 여행경로에서는 더 이상 탐색할 필요가 없으니까

 

copy_ticket에서 제거하고 여행경로의 집합 dir_list에 (여행경로, 남은 티켓들) 형태로 넣어준다

 

-------------------------------------------------------------------------------------------------------------------------

 

2번째 예제를 생각해보면

 

['ICN', 'SFO'], deque([['ICN', 'ATL'], ['SFO', 'ATL'], ['ATL', 'ICN'], ['ATL', 'SFO']])]

 

[['ICN', 'ATL'], deque([['ICN', 'SFO'], ['SFO', 'ATL'], ['ATL', 'ICN'], ['ATL', 'SFO']])

 

로 들어가 있을 것이다

 

---------------------------------------------------------------------------------------------------------------------------

 

comp_dir = []
    
while dir_list != deque():

    d,ticket = dir_list.popleft()

    for a,b in ticket:

        if d[-1] == a:

            copy_d = deepcopy(d)
            copy_ticket = deepcopy(ticket)

            copy_d.append(b)
            copy_ticket.remove([a,b])

            if copy_ticket != deque():

                dir_list.append([copy_d,copy_ticket])

            else:

                comp_dir.append(copy_d)
    


comp_dir.sort()


return comp_dir[0]

 

그러면 이제 dir_list에서 왼쪽부터 하나씩 빼서 만들어진 경로, 남아있는 ticket = d,ticket로 준다

 

그러면 이제 남아있는 ticket인 ticket에서 하나씩 순회해서 경로를 만들건데 

 

ticket에서 순회하면 a,b로 나오는데 a가 출발지점이고 이것이 리스트 d의 마지막 값 d[-1]과 일치해야 경로를 이어줄 수 있다

 

그런 a,b를 ticket에서 찾았다면 경로 d를 deepcopy하고 ticket을 deepcopy한다음에

 

copy_d에 출발지점 a에 대한 도착지점 b를 넣어서 경로를 이어주고

 

copy_ticket에서는 탐색된 [a,b]를 제거한다

 

그런 다음 copy_ticket가 여전히 남아있다면 모든 ticket을 사용하지 않은 것이므로 dir_list에 (만들어진 경로, 남아있는 티켓)형태로 넣어주고

 

copy_ticket가 deque()로 비어있다면 모든 ticket을 사용해서 경로 copy_d가 만들어졌으므로 완성된 경로를 담은 comp_dir에 넣어준다

 

deepcopy했기때문에 원본인 d와 ticket는 copy_d, copy_ticket를 remove해도 변경되지 않는단말이지 

 

-------------------------------------------------------------------------------------------------------------------------------------------------예를 들어서 생각해보면 

 

[['ICN', 'ATL'], deque([['ICN', 'SFO'], ['SFO', 'ATL'], ['ATL', 'ICN'], ['ATL', 'SFO']])

 

이런 경우에 d=['ICN', 'ATL']인데 d[-1]='ATL'이고 ticket = deque([['ICN', 'SFO'], ['SFO', 'ATL'], ['ATL', 'ICN'], ['ATL', 'SFO']])인데

 

ticket에서 하나씩 순회하면 맨 처음으로 d[-1]='ATL'와 a가 같은 경우는 ['ATL','ICN']이다

 

그러면 copy_d = ['ICN','ATL','ICN'], copy_ticket = deque([['ICN', 'SFO'], ['SFO', 'ATL'], ['ATL', 'SFO']])이고 dir_list에 들어간다

 

하지만 for문은 여전히 순회중이고 마지막 ['ATL','SFO']에서 d[-1]='ATL'와 a가 같다

 

따라서 dir_list에 copy_d = ['ICN','ATL','SFO'], copy_ticket = deque([['ICN', 'SFO'], ['SFO', 'ATL'], ['ATL', 'ICN'])이 또 들어간다

 

그러므로 [['ICN', 'ATL'], deque([['ICN', 'SFO'], ['SFO', 'ATL'], ['ATL', 'ICN'], ['ATL', 'SFO']])를 처리하고 나면

 

dir_list에는..

 

['ICN', 'SFO'], deque([['ICN', 'ATL'], ['SFO', 'ATL'], ['ATL', 'ICN'], ['ATL', 'SFO']])]는 설명안했지만 처리했다고 가정하고

 

 

['ICN', 'SFO', 'ATL'], deque([['ICN', 'ATL'], ['ATL', 'ICN'], ['ATL', 'SFO']])],

 

[['ICN', 'ATL', 'ICN'], deque([['ICN', 'SFO'], ['SFO', 'ATL'], ['ATL', 'SFO']])],

 

[['ICN', 'ATL', 'SFO'], deque([['ICN', 'SFO'], ['SFO', 'ATL'], ['ATL', 'ICN']])]])

 

이 차례대로 들어가 있을 것이다

 

그러면 다시 ['ICN', 'SFO', 'ATL'], deque([['ICN', 'ATL'], ['ATL', 'ICN'], ['ATL', 'SFO']])] 부터 d,ticket로 주어서 반복탐색을 시작할 것

 

[['ICN', 'SFO', 'ATL', 'ICN', 'ATL'], deque([['ATL', 'SFO']])],

 

[['ICN', 'ATL', 'ICN', 'SFO', 'ATL'], deque([['ATL', 'SFO']])],

 

[['ICN', 'ATL', 'SFO', 'ATL', 'ICN'], deque([['ICN', 'SFO']])]])

 

계속 반복하면 위와 같이 남은 ticket이 하나인경우까지 나오고

 

[['ICN', 'SFO', 'ATL', 'ICN', 'ATL'], deque([['ATL', 'SFO']])]을 처리할 때 

 

copy_d가 ['ICN', 'SFO', 'ATL', 'ICN', 'ATL','SFO']가 되면서 copy_ticket는 deque()가 되어가지고 모든 ticket을 사용한 경로가 완성되었다는 의미니까

 

comp_dir에 ['ICN', 'SFO', 'ATL', 'ICN', 'ATL','SFO']가 먼저 들어간다

 

그래서 

 

[['ICN', 'SFO', 'ATL', 'ICN', 'ATL', 'SFO'], ['ICN', 'ATL', 'ICN', 'SFO', 'ATL', 'SFO'], ['ICN', 'ATL', 'SFO', 'ATL', 'ICN', 'SFO']]

 

으로 그림판으로 예상한것처럼 3가지 경로가 완성된다

 

그런데 조건에서 경로가 여러개면 알파벳 순서가 앞서는 경로를 return하라고 했으므로 comp_dir.sort()로 정렬을 수행

 

그러면 알파벳 순서대로 오름차순된

 

[['ICN', 'ATL', 'ICN', 'SFO', 'ATL', 'SFO'], ['ICN', 'ATL', 'SFO', 'ATL', 'ICN', 'SFO'], ['ICN', 'SFO', 'ATL', 'ICN', 'ATL', 'SFO']]

 

이 나오고 0번째 원소 comp_dir[0]가 정답이 된다

 

 

5. 다른 풀이

 

def solution(tickets):

    routes = {}
    
    for t in tickets:
    
        routes[t[0]] = routes.get(t[0], []) + [t[1]]
        
    for r in routes:
    
        routes[r].sort(reverse=True)
        
    stack = ["ICN"]
    
    path = []
    
    while len(stack) > 0:
    
        top = stack[-1]
        
        if top not in routes or len(routes[top]) == 0:
        
            path.append(stack.pop())
            
        else:
        
            stack.append(routes[top][-1])
            
            routes[top] = routes[top][:-1]
            
    return path[::-1]

 

tickets를 순회해서 t라고 주고 t[0]는 출발점, t[1]은 t[0]의 도착점인데

 

routes.get(t[0],[]) + t[1]은 routes에서 t[0]의 value + t[1]을 하라는 의미

 

t[0]의 value가 없으면 [] + t[1]을 하라는 의미

 

[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]을 예로 들어서 생각해보면

 

 

 

['ICN', 'SFO']이면 routes['ICN']은 없으므로 routes.get('ICN',[]) = []이고 t[1] = 'SFO'이므로

 

 

{'ICN':['SFO']}

 

 

다음 ['ICN','ATL']이면 routes.get['ICN',[]) = ['SFO']이고 t[1] = 'ATL'이므로

 

 

{'ICN':['SFO','ATL']}

 

 

['SFO','ATL']이면 routes.get('SFO',[]) = []이고 t[1] = 'ATL'이므로

 

 

{'ICN':['SFO','ATL'], 'SFO':['ATL']}

 

 

마찬가지로 ['ATL','ICN'], ['ATL','SFO']도 처리하면

 

 

{'ICN':['SFO','ATL'], 'SFO':['ATL'], 'ATL':['ICN','SFO']}

 

 

for r in routes:
    
    routes[r].sort(reverse=True)

 

다음 위와 같은 코드를 생각해보면 dict인 routes에서 for문으로 단순 순회하면 key를 불러온다

 

그러니까 r은 'ICN', 'SFO', 'ATL'이고.. routes[r]은 ['SFO','ATL'], ['ATL'], ['ICN','SFO']가 되고

 

sort(reverse=True)는 내림차순 정렬한다

 

{'ICN': ['SFO', 'ATL'], 'SFO': ['ATL'], 'ATL': ['SFO', 'ICN']}으로 될것

 

stack = ["ICN"]
    
path = []

while len(stack) > 0:

    top = stack[-1]

    if top not in routes or len(routes[top]) == 0:

        path.append(stack.pop())

    else:

        stack.append(routes[top][-1])

        routes[top] = routes[top][:-1]

 

stack = ['ICN']은 첫 출발공항을 초기화한 것 같고 path = []은 경로를 담을 리스트일테고

 

stack의 길이가 양수이면 while 반복문을 계속 돈다

 

stack의 마지막 stack[-1]을 top으로 두고 현재 top = 'ICN'인데

 

dict의 in연산자는 dict의 key에 들어가는지 안들어가는지를 검사한다.

 

그래서 top not in routes는 'routes의 key ['ICN', 'SFO', 'ATL']에 top이 존재하지 않는다'를 의미하고

 

len(routes[top])은 routes[top]의 개수를 의미할테지

 

그러면 현재 'ICN'은 routes의 key에 존재하면서 routes['ICN'] = ['SFO','ATL']의 개수는 0이 아니니까.. else문으로 들어가서

 

routes['ICN'] = ['SFO','ATL']의 마지막 원소 'ATL'을 빼서 stack = ['ICN','ATL']로 만들고

 

routes['ICN'] = ['SFO']로 만든다

 

그러면 다시 top = 'ATL'이고 routes['ATL'] = ['SFO','ICN']이고 'ICN'을 stack에 넣어서 ['ICN','ATL','ICN']으로 만든다

 

routes['ATL'] = ['SFO']로 만들고

 

다시 top = 'ICN'으로 하고 routes['ICN'] = ['SFO']의 마지막 원소 'SFO'를 빼서 ['ICN','ATL','ICN','SFO']로 만들고

 

routes['ICN'] = []으로 만든다

 

다시 top = 'SFO'인데 routes['SFO'] = ['ATL']인데 마지막 원소 'ATL'을 빼서 ['ICN','ATL','ICN','SFO','ATL']로 만들고

 

routes['SFO'] = []으로 만든다

 

다시 top = 'ATL'인데 routes['ATL'] = ['SFO']에서 마지막 원소 'SFO'를 빼서 ['ICN','ATL','ICN','SFO','ATL','SFO']로 만들고

 

routes['ATL'] = []으로 만든다

 

그러면 top = 'SFO'인데 문제는 routes['SFO'] = []으로 길이가 0이므로 이제 stack의 마지막 'SFO'를 빼서 path에 넣어준다

 

모든 경우 routes는 현재 value가 []으로 길이가 0이므로 path = ['SFO','ATL','SFO','ICN','ATL','ICN']이 된다

 

그리고 stack = []이니까 while문을 탈출하고 path를 역순으로 배열한 path[::-1] = ['ICN','ATL','ICN','SFO','ATL','SFO']를 return한다 

 

시간복잡도가 매우 효율적인데 문제는 코드가 직관적이지가 않다

 

내가 모르는 알고리즘이 들어간건지 모르겠지만

 

routes의 초기화 {'ICN':['SFO','ATL'], 'SFO':['ATL'], 'ATL':['ICN','SFO']}는 뭐 출발공항: 도착공항리스트겠지만

 

routes의 value들을 역순배열하고.. while 반복문 내용이 뭔가 억지같은데

--------------------------------------------

 

from collections import defaultdict 

def dfs(graph, N, key, footprint):

    if len(footprint) == N + 1:
        return footprint

    for idx, country in enumerate(graph[key]):
        graph[key].pop(idx)

        tmp = footprint[:]
        tmp.append(country)

        ret = dfs(graph, N, country, tmp)

        graph[key].insert(idx, country)

        if ret:
            return ret


def solution(tickets):
    answer = []

    graph = defaultdict(list)

    N = len(tickets)
    for ticket in tickets:
        graph[ticket[0]].append(ticket[1])
        graph[ticket[0]].sort()

    answer = dfs(graph, N, "ICN", ["ICN"])

    return answer

 

solution함수부터 먼저 살펴보면 graph를 defaultdict(list)로 초기화하는데 defaultdict는 value의 기본값을 지정하는 것으로

 

list로 지정한다는 소리는 모든 key의 value 초기값이 []이라는 의미

 

tickets에서 순회해서 ticket라 하고 ticket[0]는 출발점이고 ticket[1]은 도착점이고 출발점에 대응하는 도착점을 넣어서 graph로 만든다

 

도착점들은 sort()해서 알파벳 순으로 한다는 것인데

 

defaultdict(<class 'list'>, {'ICN': ['ATL', 'SFO'], 'SFO': ['ATL'], 'ATL': ['ICN', 'SFO']}) 이런 식으로 나옴

 

여기까지는 뭐 출발점에 대응하는 도착점들을 묶어놓은거니까 그렇다치는데

 

그러면 이제 dfs()함수에 넣어서 answer를 구한다는데 dfs()함수가 뭐기에

 

def dfs(graph, N, key, footprint):

    if len(footprint) == N + 1:
        return footprint

    for idx, country in enumerate(graph[key]):
        graph[key].pop(idx)

        tmp = footprint[:]
        tmp.append(country)

        ret = dfs(graph, N, country, tmp)

        graph[key].insert(idx, country)

        if ret:
            return ret

 

footprint는 아마 path를 의미하겠지 ['ICN']을 넣은것 보니까? 길이가 N+1이 되면 footprint를 return하고

 

graph에 key를 넣어서 순회를 하는데 첫 key가 ICN이잖아

 

['ATL','SFO']를 순회하는데

 

먼저 graph[key].pop(idx)하면 graph[key] = ['SFO']가 될거고 tmp = footprint[:] = ['ICN']으로 초기화하고

 

country = 'ATL'인데 tmp에 넣으면 ['ICN','ATL']

 

출발점 key에 대응하는 도착점 'ATL'을 넣은거고 dfs()함수에 country = 'ATL', tmp = ['ICN','ATL']을 넣어서 재귀함수를 만들구나

 

ret를 재귀함수로 구하고 그리고 graph[key] = ['SFO']에서 insert함수로 현재 idx=0, country = 'ATL'을 graph[key]에 넣어서 ['ATL','SFO']로 다시 만드네?

 

근데 문제는 ret를 구하는 dfs()에는 graph['ICN'] = ['SFO']인 상태로 들어간다는 거지

 

defaultdict(<class 'list'>, {'ICN': ['SFO'], 'SFO': ['ATL'], 'ATL': ['ICN', 'SFO']})에다가 ['ICN','ATL'] 상태로 dfs()함수를 돌리는데

 

그리고 다음 idx = 1, country = 'SFO'인데 먼저 pop하니까 graph의 상태는

 

defaultdict(<class 'list'>, {'ICN': ['ATL'], 'SFO': ['ATL'], 'ATL': ['ICN', 'SFO']})일테고

 

현재 footprint = ['ICN']에서 tmp = ['ICN']이고 여기에 SFO를 넣어서 ['ICN','SFO']를 다시 dfs()로 넣는다

 

그러면 defaultdict(<class 'list'>, {'ICN': ['ATL'], 'SFO': ['ATL'], 'ATL': ['ICN', 'SFO']})에다가 ['ICN','SFO']상태로 dfs()를 돌리는거네

 

근데 문제는 이제 return값은 하나란 말이야 for문은 두번 돌아서 ret가 2개인데

 

즉 보면은 defaultdict(<class 'list'>, {'ICN': ['SFO'], 'SFO': ['ATL'], 'ATL': ['ICN', 'SFO']})에다가 ['ICN','ATL'] 상태로 dfs()함수를 돌린 ret가 정상적으로 return이 되면 얘를 먼저 return할 것임

 

이건 가능한 경로가 여러개면 알파벳 순으로 앞에 오는 것을 return해야하기 때문에

 

그래서 graph[ticket[0]].sort()도 했구나 알파벳 순으로 앞에 오는게 먼저 dfs()되도록

 

-------------------------------------------------------------------------------------------------------------------------------------------------

 

아무튼 그러면 계속 생각해볼까?

 

defaultdict(<class 'list'>, {'ICN': ['SFO'], 'SFO': ['ATL'], 'ATL': ['ICN', 'SFO']})에다가 ['ICN','ATL']가 들어가면..

 

현재 key = 'ATL'이고 그래서 graph[key] = ['ICN','SFO']를 순회하는데

 

idx = 0, country = 'ICN'에서 graph[key] = ['SFO']로 만든다음

 

footprint = ['ICN','ATL']에서 tmp = ['ICN','ATL']로 초기화하고 country에 ['ICN']을 넣고

 

defaultdict(<class 'list'>, {'ICN': ['SFO'], 'SFO': ['ATL'], 'ATL': ['SFO']})에다가 ['ICN','ATL','ICN']을 dfs()로 탐색한다.

 

........ 그러면 이걸 계속해서 반복하면?

 

defaultdict(<class 'list'>, {'ICN': [], 'SFO': ['ATL'], 'ATL': ['SFO']})에다가 ['ICN','ATL','ICN','SFO']

 

defaultdict(<class 'list'>, {'ICN': [], 'SFO': [], 'ATL': ['SFO']})에다가 ['ICN','ATL','ICN','SFO','ATL']이 들어가고

 

여기서 이제 key = 'ATL'에서 graph가 defaultdict(<class 'list'>, {'ICN': [], 'SFO': [], 'ATL': []})으로 되고

 

['ICN','ATL','ICN','SFO','ATL','SFO']가 tmp가 되어서 마지막으로 

 

defaultdict(<class 'list'>, {'ICN': [], 'SFO': [], 'ATL': []})와 ['ICN','ATL','ICN','SFO','ATL','SFO']이 dfs()에 들어가는데

 

N이 ticket의 수이고 footprint는 ['ICN','ATL','ICN','SFO','ATL','SFO']인데 ticket 다 쓰면 footprint가 N+1이 되는구나?

 

[a,b], [b,c], [c,d] 3개이면 a-b-c-d로 4개..

 

[a,b],[b,c],[c,d],[e,f] 4개이면 a-b-c-d-e-f로 5개

 

그러면 footprint가 N+1이니까 우리는 바로 ['ICN','ATL','ICN','SFO','ATL','SFO']을 return해서 최초 ret값이 ['ICN','ATL','ICN','SFO','ATL','SFO']이 되고 얘는 길이가 0이 아니니까 얘를 바로 return하면 되네?

 

이건 진짜 지리긴하네 시간도 엄청 빠르고 코드도 직관적으로 이해하기 쉽다고 해야하나

 

확실히 시간이 빠를수밖에 없는 이유가 나는 모든 경로를 탐색하고 거기서 가장 빠른 경로를 찾아왔는데

 

시간이 빠른 코드들은 모든 경로를 찾아가지 않고 애초에 알파벳이 빠른 경로를 찾아간다는 점이네

 

그리고 pop, insert도 지린다고 해야하나

 

-----------------------------------------------------------------

 

6. 되돌아보기

 

비효율적이긴 했지만 상당히 잘 했다

 

deepcopy, deque이용해서 트리구조를 완전히 탐색하는 방법

 

생각 잘하면 돼

 

그리고 다른 풀이에서 재귀함수로 dfs를 구현했던거 기억하면 좋을것 같은데

 

특히 for문 돌면서 pop insert한거 지리긴했어

 

애초에 dfs를 구현할때 위와같이 스택과 재귀함수로 구현하는게 기본인가봐

 

연습 많이해야겠다