알고리즘 유형 : BFS/DFS
풀이 참고 없이 스스로 풀었나요? : X
https://school.programmers.co.kr/learn/courses/30/lessons/43164
SOLVE 1
DFS(재귀) 풀이
def solution(tickets):
answer = []
# 출발지가 같은 티켓끼리 쭉 나열되도록 출발지 기준 정렬
# 같은 출발지에 대해서 도착지 기준 정렬(알파벳 순서 상 앞에꺼 먼저 방문하기 위함)
tickets.sort(key = lambda x: (x[0], x[1]))
# DFS
def getPath(t, path):
# 티켓을 모두 소진했다면 현재까지의 path 그대로 리턴
if len(t) == 0:
return path
now = path[-1]
valid_idx = -1
# 남은 티켓(정렬된 상태) 중에서, 출발지가 현재 공항인 티켓의 인덱스를 찾음
# 조건을 만족하는 티켓 중 가장 왼쪽의 티켓에서 멈춤
for i in range(len(t)):
if t[i][0] == now:
valid_idx = i
break
# len(t) == 0이 아니었으므로 티켓이 남아있다는건데 나아갈 공항이 없다는 것은
# 유효한 루트가 아니라는 뜻이므로 실패의 의미에서 빈 리스트 리턴
if valid_idx == -1:
return []
# 출발지가 현재 공항인 티켓을 모두 순회하면서 DFS 돌림
# 하나라도 먼저 완성된 루트가 나온다면 그걸 리턴해줌
# 같은 출발지 기준, 도착지를 기준으로 오름차순 정렬했었기 때문에
# 먼저 완성된 루트가 나온다면 그게 곧 알파벳 순서 상 가장 앞선 루트가 됨
while t[valid_idx][0] == now:
nxt_path = getPath(t[:valid_idx] + t[valid_idx + 1:], path + [t[valid_idx][1]])
if nxt_path != []:
return nxt_path
valid_idx += 1
return []
return getPath(tickets, ["ICN"])SOLVE 2
DFS(스택) 풀이
from collections import defaultdict
def solution(tickets):
t_dict = defaultdict(list)
# key: 출발지, value: 목적지인 딕셔너리 만듦
for s, e in tickets:
t_dict[s].append(e)
# 목적지 기준 내림차순 정렬(맨 오른쪽걸 pop해서 쓸거임. 알파벳 순서 상 가장 앞선 것)
for t_key in t_dict.keys():
t_dict[t_key].sort(reverse = True)
answer = []
path = ["ICN"]
# DFS를 실행함. 처음에는 맨 마지막 공항까지 쭉쭉 나아감.
# 어느 순간 다른 공항으로 가는 티켓도 없고, 또는 그런 티켓을 다 소진한
# 어떤 공항에 도착한다면 그 곳이 맨 마지막에 도달하게 될 공항임.
# 이제 path에서 pop해서 하나씩 answer에 넣어줌으로써 path를 역방향으로
# 거슬러 올라갈거임. 다만 맨 마지막 공항에 처음으로 도착했을 때의 path
# 가 모든 간선을 다 사용하지 않은 path일 수도 있음. 그러므로, 한 칸씩
# 내려가면서 그 공항과 연결된 인접 공항들을 싹 다 돌아주면 됨.
# 이렇게 ICN까지 쭉 실행해주면 path는 비게 되고 answer에는 역방향의 정답
# 루트가 담겨있게 됨.
while path:
now = path[-1]
if now not in t_dict or len(t_dict[now]) == 0:
answer.append(path.pop())
else:
path.append(t_dict[now].pop())
return answer[::-1]SOLVE 3
BFS 풀이
from collections import deque
def solution(tickets):
answer = []
# 출발지, 목적지 기준 정렬
# 출발지를 기준으로 정렬하면 출발지가 같은 것끼리 인접하도록 정렬되고,
# 특정 공항이 출발지인 티켓을 쉽게 연속적으로 순회 가능함
# 목적지를 기준으로 정렬하면 알파벳 순서 상 앞선 도착지를 먼저 방문할 수 있으므로,
# 최초의 완성 루트를 발견하면 그게 곧 알파벳 순서 상 가장 앞선 완성 루트가 됨
tickets.sort(key = lambda x: (x[0], x[1]))
# 현재까지의 경로와, 남은 티켓을 큐에 튜플로 저장
dq = deque([(["ICN"], tickets)])
while dq:
now_path, now_t = dq.popleft()
# 남은 티켓이 없다면, 그 때의 path가 알파벳 순서 상 가장 앞선 완성된 루트임
if len(now_t) == 0:
answer = now_path
break
# 출발지가 현재 위치한 공항과 같은 티켓 중 가장 왼쪽 거에서 idx를 멈춤
valid_idx = -1
for i in range(len(now_t)):
if now_t[i][0] == now_path[-1]:
valid_idx = i
break
# 남은 티켓이 있는 상태에서 다른 공항으로 가는 티켓도 없으므로 현재 루트는
# 유효하지 않은 루트이므로 continue
if valid_idx == -1:
continue
# 출발지가 현재 위치한 공항인 티켓을 차례로 순회하며 정보를 큐에 넣어줌
while valid_idx < len(now_t) and now_t[valid_idx][0] == now_path[-1]:
dq.append((now_path + [now_t[valid_idx][1]], now_t[:valid_idx] + now_t[valid_idx+1:]))
valid_idx += 1
return answerSOLVE 1) 풀이 요약 (DFS(재귀) 풀이)
-
해당 문제는 주어진 모든 간선을 다 거쳐야하고, 탐색 경로도 찾아야하는 문제이다. (모든 간선을 거치면 모든 노드를 탐색할 수 있다는 것은 문제의 조건에서 보장되어 있음)
즉, 탐색의 완료 조건은 모든 간선을 다 거치는 것이다.
다만 주어진 그래프는 단방향 그래프이므로, 항상 모든 간선을 다 거칠 수는 없다. 즉, 모든 간선을 다 거칠 수 있는 특정 경로들을 찾아야한다.
-
우선 처음 출발 위치인 ICN에서 DFS를 실행한다.
DFS의 리턴 값은 "모든 간선을 다 거치는 경로 중에서 알파벳 기준 사전 상 가장 앞선 경로"이다. 한 마디로 정답을 리턴한다.
DFS의 매개 변수는
남은 티켓과현재까지의 경로이다.남은 티켓을 매개 변수로 줌으로써 이미 방문한 간선을 제외할 수 있고, 남은 티켓의 개수로 종료 조건을 세울 수 있다.현재까지의 경로를 매개 변수로 줌으로써 거쳐온 루트를 기록할 수 있고, 마지막 원소를 조회하여 현재 위치한 공항을 알 수 있다.종료 조건을 알았으니, 이제 인접 노드를 탐색하는 구문을 작성해야된다.
-
간선 정보는 매개변수로 받은
남은 티켓리스트에 있다. 그런데 현재 공항이 출발지인 티켓을 찾으려니 리스트를 다 돌아야하는데 시간복잡도 측면에서 좀 부담스럽다. 그래서, 맨 처음에 tickets를 출발지 기준으로 한 번 정렬해주자.자 이제 인접 노드를 순회할 수 있게 됐다. 남은 티켓 리스트에서 출발지가 현재 위치한 공항인 티켓이 나오는 최초 인덱스를 valid_idx에 구하고, 그 인덱스로부터 출발지가 달라지는 티켓 직전까지의 티켓이 모두 인접 노드로 향하는 티켓에 해당한다. (만약 남은 티켓이 있는 상태에서 valid_idx가 여전히 -1인 채로 갱신되지 않았다면 인접 공항으로 가는 간선이 하나도 없다는 뜻이고, 이 것은 곧 현재 가고 있는 루트가 실패 루트라는 것을 의미하므로 백트래킹해준다(continue))
이제 DFS를 돌면서 완성된 경로를 찾으면 된다.
그런데 여기서 시간복잡도를 더 줄일 수 있는 방법이 있다.
그냥 쌩으로 다 돌고 얻은 모든 완성 경로를 또 정렬해서 정답을 찾기에는 시간복잡도가 꽤 크다.
처음에 티켓 리스트를 정렬할 때 출발지 기준으로 정렬했었는데, 여기에 sort key에 도착지를 추가해서 같은 출발지인 티켓을 도착지 기준으로 정렬해주게 되면, 인접 노드를 돌 때 알파벳 순서 상 가장 앞선 도착지를 먼저 방문할 수 있다. 이런 식으로 탐색을 돌게 되면 가장 처음 발견한 완성 경로가 곧 답이 된다.
SOLVE 2 풀이 요약 (DFS(스택) 풀이)
-
스택을 활용한 DFS 풀이이다.
우선 간선 정보(티켓)를 딕셔너리에 담아준다. key가 출발지, value가 목적지이다.
이 후 딕셔너리의 value에 해당하는 리스트들을 모두 각각 내림차순 정렬해준다. DFS를 돌면서, 인접 노드(도착지)를 고를 때 pop해서 쓸건데 내림차순 정렬하면 pop되는 노드는 알파벳 순서 상 가장 앞선 노드이다. 이렇게 하면 solve 1에서 설명했듯이 맨 처음 찾은 완성 경로를 바로 정답으로 삼고 탐색을 종료할 수 있어 시간복잡도 측면에서 유리하다.
-
DFS에서, path에 순회 중 현재까지의 방문 경로를 저장해나간다.
우선은 맨 마지막 공항까지 쭉죽 나아간다. 마지막 공항이라는 것은 그 공항에서 다른 공항으로 가는 티켓이 아예 없거나, 있었는데 이미 다 쓴 상태인 공항을 의미한다.
그러한 공항에 도착했다면 그 곳이 맨 마지막에 도달하게 될 공항이다.
이제 path에서 하나씩 pop해서 answer에 추가해나갈것이다. 이렇게 되면 path를 역방향으로 가면서 계속 pop해나가는건데, path에 있는 걸 다 뽑았다고해서 그게 정답임이 보장되진 않는다.
출발지인 ICN으로부터 맨 마지막 노드까지의 경로이긴 하지만, 아직 사용하지 못한 간선이 남아있는 상태에서의 path 일수있기 때문이다.
그래서, path에서 하나씩 pop하여 answer에 추가해나가면서, path의 맨 마지막 원소에 대해 아직 처리하지 못한 간선이 남아있다면 그 간선의 도착지를 path(스택)에 추가하여 마저 처리해주는 식으로 끝까지 진행한다.
이런 식으로 쭉 가서 마지막에는 ICN을 pop해서 answer에 넣고 stack(path)이 비기에 반복문이 종료된다.
역방향으로 answer에 넣어줬으니 뒤집어서 리턴해주면 끝
SOLVE 3 풀이 요약 (BFS 풀이)
-
solve 1이랑 매커니즘이 거의 똑같다.
티켓을 출발지, 도착지 기준 정렬해주고, BFS를 돈다.
큐에는 path와 남은 티켓 리스트가 튜플 형태로 들어가고, 반복문에서 종료 조건은 남은 티켓이 0인 시점이다.
만약 남은 티켓이 있는데 다른 공항으로 가는 티켓이 없는 경우 현재 위치한 공항까지의 루트는 실패 루트이므로 continue 해준다.
현재 순회 중 공항이 출발지인 티켓을 차례로 순회하면서 남은 티켓과 path를 갱신하여 큐에 넣어준다.
배운 점, 어려웠던 점
- solve 2 스택 풀이를 이해하는 데 한참 걸렸다.. 아직 DFS, 특히 스택 DFS와 백트래킹의 활용이 많이 미숙한 것 같다. 경험을 많이 쌓을 필요를 느꼈다.
