깊이 우선 탐색(DFS;Depth-First Search)
한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하되, 인접 정점을 기준으로 깊이 우선 탐색을 끝낸 후 다음 정점으로 진행
ex)
무방향그래프
0 - 1 - 3 - 7 - 4 - 5- 2- 6 순 방문
0에서 출발 → 1 방문했다면 3과 4로 방문할 수 있다
3을 방문하면 7로 진행할 수 밖에 없다. 그러면 0 - 1 - 3 - 7로 방문
이후 7에서는 아까 1에서 방문할 수 있던 노드였던 4로 진행하고 4에서는 이제 방문할 수 있는 인접 노드가 없다 : 0 - 1 - 3 - 7 - 4
그럼 이제 7에서 방문할 수 있는 노드인 5를 방문
5에서는 2로 진행할 수 있다 : 0 - 1 - 3 - 7 - 4 - 5 - 2
마지막 남은 노드인 6을 방문하며 깊이 우선 탐색을 끝낸다. : 0 - 1 - 3 - 7 - 4 - 5- 2- 6 → 예시를 보면 알겠지만 유일한 방문 순서는 아님
이를 구현하기 위해서는 stack으로 어느 정점에서 DFS를 하고 있는지 기억해 되돌아가야 합니다. 재귀적인 성질을 가집니다.
너비 우선 탐색 (BFS; Breadth-First Search)
한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문한 후, 방문한 각 인접 정점을 기준으로 방문한 순서에 따라 또 다시 너비 우선 탐색을 시행한다.
ex)
무방향그래프
0에서 출발
0에서 인접한 노드는 1과 2가 있다. 그럼 0 - 1 - 2 탐색
먼저 방문한 1에 대해 너비 우선 탐색 → 3과 4 방문
그 다음 방문한 2에 대해 너비 우선 타색 → 5와 6 방문
남은 7 방문
: 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7
이것 역시 유일한 순서는 아님
이를 구현하기 위해서는 큐를 이용해 어느 노드에서 BFS를 해야 하는지 기록하고 진행해야 합니다.
문제
주어진 항공권을 모두 이용해 여행 경로를 짜려고 합니다.
항상 "ICN"공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담에 return하도록 solution함수를 작성해주세요
[제한]
•
모든 공항은 알파벳 대문자 3글자
•
주어진 공항 수는 3~10000
•
tickets의 각 행 [a, b]는 a공항에서 b공항으로 가는 항공권이 있다는 의미
•
주어진 항공권 모두 사용해야 함
•
만일 가능 경로가 2개 이상이라면 알파벳 순서가 앞서는 경로 return
•
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
공항들이 node이고 항공권이 edge의 방향을 알려주는 방향그래프를 그릴 수 있겠군요
기본 보기
Search
모든 정점을 방문하는 문제가 아니고, 모든 간선을 거쳐야 하는 문제임을 명심해야 합니다.
항공권 사용 순서를 결정해야 하는 것인데, 한 정점에서 선택할 수 있는 간선이 2개 이상이라면 공항 알파벳 순서를 따르면 될 것입니다(문제의 조건)
알고리즘
출발지인 ICN에서 선택할 수 있는 정점은 ATL과 SFO인데, 알파벳이 앞서는 ATL을 선택합시다!
ATL에서는 ICN으로 되돌아가는 방법과 SFO로 가는 방법이 있네요 ICN이 알파벳에서 더 앞서니 다시 돌아가줍시다 : ICN - ATL - ICN
이젠 SFO로 가는 방법밖에 없죠?
SFO - ATL - SFO로 남은 항공권을 소진해주면 되겠습니다.
: ICN - ATL - ICN - SFO - ATL - SFO
어디로 갈 지 판단하는 계속 같은 동작을 반복하는 면에서 재귀적인 면이 보입니다.
stack을 통해 재귀적인 '한 붓 그리기' 문제를 해결합니다 → DFS의 응용입니다.
이 알고리즘은 어떻게 동작하는 걸까요?
다음과 같은 예시에서, 출발지는 항상 ICN이므로 stack에는 ICN이 일단 들어있습니다.
다음 방문 공항은 알파벳이 앞서는 AAA로 갔더니(stack에 AAA넣음), 더 이상 갈 수 있는 곳이 없습니다.
: 더이상 갈 수 있는 곳이 없는 경우 - 1. 여행경로 끝, 2.이 공항에서 출발하는 항공권이 없음
그러면 다시 AAA를 stack에서 빼주며 ICN으로 되돌아갑니다.
AAA가 마지막 도착지겠죠? AAA를 옆에 빼두고,
그럼 다른 선택지인 BBB로 가볼까요
BBB로 이동하니 CCC로 갈 수 가 있네요
CCC에선 BBB로 이동할 수 있고, BBB에선 ICN으로, ICN에선 AAA로 이동할 수 있으므로
이렇게 되는데, stack에서 하나씩 빼면 여행경로의 역순이겠죠?
거꾸로 만들어서 return해줍니다!
풀이(코드)
그래프를 코드로 어떻게 표현할까요?
Dictionary (사전) 자료형 사용!
출발지를 key로 하고, value는 각 key인 공항에서 출발하는 항공권의 도착지의 집합을 표현합니다
여기서는
ICN : {ATL, SFO}
ATL : {ICN, SFO}
SFO : {ATL}
이렇게 되겠죠?
그런데 우리는 알파벳 순서를 이용해야하니까
집합이 아닌 list자료형을 이용해 정렬해줍시다!
ICN : [ATL, SFO]
ATL : [ICN, SFO]
SFO :[ATL]
그런데 리스트는 앞에꺼 빼는 것보다 뒤에꺼 뺴는거가 더 빠르니까 역순으로 정렬해줍시다!
pop() : , pop(0) :
ICN : [SFO, ATL ]
ATL : [SFO, ICN]
SFO :[ATL]
def solution(tickets):
routes = {}
for t in tickets:
routes[t[0]] = routes.get(t[0], []) + [t[1]] # .get(key, default) : key에 해당하는 값이 없으면 default값을 return
for r in routes : # r은 key가 됩니다.
routes[r].sort(reverse=True)
stack = ["ICN"] # 무조건 출발지는 ICN
path = [] # 경로를 저장
while len(stack) > 0 :
top = stack[-1]
if top not in routes or len(routes[top]) == 0: # top이 key인 값이 없거나 있는데 빈 리스트인 경우, 즉 해당 공항에서 더 이상 진행 불가인 경우
path.append(stack.pop())
else: # 진행 가능한 경우
stack.append(routes[top].pop()) # 해당 공항에서 갈 수 있는 도착지 공항중 알파벳이 앞서는 것을 선택해 stack에 쌓는다
return path[::-1] # path는 역순으로 저장되어 있으므로 순서 뒤집어 return
Python
복사
이 알고리즘의 복잡도는
for r in routes : # r은 key가 됩니다.
routes[r].sort(reverse=True)
이 부분에 지배됩니다
while문 부분은 이미 정렬된 상태로 이뤄지기 때문에 Linear한 시간 복잡도를 갖게됩니다.
