난이도 : 레벨 3
유형 : DFS
출처 : https://school.programmers.co.kr/learn/courses/30/lessons/43164
문제 파악
주어진 항공권 (tickets 배열)을 이용하여 여행 경로(배열)를 짜려고 한다.
항상 시작 공항은 "ICN" 공항이다. 모든 도시를 방문할 수 없는 경우는 애초에 주어지지 않는다.
두번째 입출력 예를 보면
tickets 배열
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]
를 입력 받아서
["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 를 return한다.
첫 "ICN" 에서 갈 수 있는 곳이 SFO, ATL 이지만 문제 조건에 따라 알파벳이 더 빠른 ATL을 갔다가 다시 ICN을 간다.
즉 이 문제는 방향이 있는 그래프이고 한 노드에서 나가는 간선이 두개라면 알파벳이 더 빠른 간선을 택하며 모든 경로를 완성해야하는 문제이다.
처음엔 BFS 로 풀려고 했지만 BFS 는 적절하지 않은 아이디어이다. 왜냐하면 BFS는 모든 경로를 탐색하지 않고 최단경로를 찾을 때 간편한 알고리즘이다.
이 경우 모든 경로를 탐색하여 여행 경로를 완성해야 하므로 DFS 가 더 적절하다.
즉
티켓을 다 써서 여행 경로를 완성해야 한다.
DFS(깊이 우선 탐색)로 모든 경로를 만들어 보고,
그중 사전순으로 가장 빠른 경로를 정답으로 고른다.
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]
해답 및 풀이
def solution(tickets):
answer = [] # 가능한 모든 경로를 담을 리스트
visited = [False] * len(tickets) # 각 티켓 사용 여부
def dfs(start, path): # start : 현재 위치한 공항, path: 경로를 저장하는 리스트
if (len(path) == len(tickets) + 1): # tickets + 1 인 이유는 시작 ICN 포함
answer.append(path) # 모든 티켓을 다 쓰면 path를 answer에 append
return # 그리고 dfs 함수 종료
# 아직 티켓을 안썼다면 반복문
else:
for idx, ticket in enumerate(tickets): # enumerate 는 반복문을 돌릴 때, 인덱스와 값을 동시에 꺼내주는 함수
if (ticket[0] == start) and (not visited[idx]):
visited[idx] = True
dfs(ticket[1], path + [ticket[1]])
visited[idx] = False
dfs("ICN", ["ICN"])
answer.sort()
return answer[0]DFS는 재귀적으로 계속 들어가기에 코드를 눈으로 본다고해서 흐름을 파악하기가 어려운 것 같다.
그래서 예제 2를 입력한 흐름을 정리하며 이해하려한다.
입력 예시
tickets = [
["ICN", "SFO"],
["ICN", "ATL"],
["SFO", "ATL"],
["ATL", "ICN"],
["ATL", "SFO"]
]- 시작
- 호출: dfs("ICN", ["ICN"])
start = "ICN", path =["ICN"] - path = ["ICN"], 아직 길이 6이 안 됨 → for문 탐색 시작
- for문 순회
enumerate는 인덱스와 값을 동시에 꺼내주니까
0 ['ICN', 'SFO']
1 ['ICN', 'ATL']
2 ['SFO', 'ATL']
3 ['ATL', 'ICN']
4 ['ATL', 'SFO']이렇게 꺼낸다.
- 첫 분기: idx=0 사용 (ICN → SFO)
사용: idx=0 ,ticket = ["ICN","SFO"]
if ticket[0] = "ICN" 이 start이고 ICN은 방문한적 없으니
visited[idx = 0] 을 True 로 하고
dfs(ticket[1], path + [ticket[1]]) 호출
= dfs("SFO", ["ICN"] + ["SFO"] = ["ICN","SFO"])
호출: dfs("SFO", ["ICN","SFO"]), 이번엔 start="SFO" , path=["ICN","SFO"]
start 가 "SFO"니까 tickets 배열에서 ticket[0] 이 "SFO"가 되는 idx를 찾는다.
=> idx가 2일때 start가 "SFO"이다. 이때 값(ticket[1]) 는 "ATL" 이므로
이번엔 dfs("ATL", ["ICN","SFO","ATL"]) 가 호출된다.
.
.
.
결국 이런식으로 분기 → 재귀 호출 → 길이 6 도달 시 answer에 추가 → 되돌아가서(백트래킹) 다른 분기 재시도를 반복한다.
이 예시에선 두가지 경로가 완성된다.
["ICN","SFO","ATL","ICN","ATL","SFO"]["ICN","ATL","ICN","SFO","ATL","SFO"]
DFS가 전부 끝나면 answer.sort() 로 사전순 정렬하고
return answer[0]으로 가전 앞에 경로를 반환한다.
재귀 호출 흐름을 떠올리는 게 아직 어렵다. DFS를 이해하기위해서는 DFS 문제만 다시 쉬운것부터 풀어야 할 것 같다.
