[프로그래머스 Lv.3] 여행경로 (DFS)

1. 문제 설명

2. 제한사항

3. 입출력 예

4. 문제 풀이

1) 깊이 우선 탐색(DFS)

• 한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하되, 각 인접 정점을 기준으로 깊이 우선 탐색을 끝낸 후 다음 정점으로 진행
• 스택을 이용하여 어느 정점에서 DFS를 하고 있는지를 기억하고 되돌아감

2) 너비 우선 탐색(BFS)

• 한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하고, 방문한 각 인접 정점을 기준으로 (방문한 순서에 따라) 또 다시 너비 우선 탐색을 행함
• 큐를 이용하여 어느 정점에서 BFS를 해야 하는지를 기록하고 진행함

3) 문제 해결 - DFS 알고리즘 응용

• 스택을 이용하여 재귀적인 "한 붓 그리기" 문제를 해결

  • 이것이 가능하다는 것은 문제에서 보장되어 있음
  • 재귀적인 성질을 가진 "한 붓 그리기" 문제는 재귀적인 성질을 가진 "그래프의 깊이 우선 탐색"을 응용하여 해결할 수 있음

• 시작 정점은 언제나 "ICN"

• 모든 정점 방문이 아니고, 모든 간선을 거쳐야 함

  • 언젠가 한 번 가야 하는데 그 순서를 결정해야 함

• 한 정점에서 택할 수 있는 간선이 두 개 이상인 경우

  • 공항 이름의 알파벳 순서를 따름

4) 출발지별 항공권 개수 카운트

from collections import deque

def solution(tickets):
    answer = []
    stack = deque()
    visited = [False] * len(tickets)
    
    tickets.sort() # 출발 공항 이름의 알파벳 기준으로 정렬
    
    # 출발지별 항공권의 개수를 카운트해서 사전으로 만듦
    path = {}
    for ticket in tickets:
        path[ticket[0]] = path.get(ticket[0], 0) + 1
        
    stack.append("ICN")
    # stack이 빌 때까지 path에 항공권을 모두 추가
    while len(stack) > 0:
        pos = stack[-1] # 출발지
        next_pos = "ZZZ" # 도착지
        # 항공권의 개수가 1이상이면 stack에 삽입하고 방문 표시
        if path.get(pos, 0) > 0:
            for k in range(len(tickets)):
                if visited[k] == False and tickets[k][0] == pos:
                	# 출발지가 같은 도착지가 여러개이면 알파벳 순서를 따름
                    if next_pos[0] > tickets[k][1][0]:
                        next_pos = tickets[k][1]
                        next_num = k
            path[pos] = path.get(pos, 0) - 1
            visited[next_num] = True
            stack.append(next_pos)
        else: # 항공권의 개수가 0이하이면 stack에서 꺼내서 path에 추가
            answer.append(stack.pop())
    answer.reverse() # path의 역순이 방문하는 공항 경로가 됨
    return answer

5) 출발지별 도착지들을 인접 리스트로 생성

• 사전을 이용하여 각 공항에서 출발하는 항공권의 리스트를 표현

  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]]
    # 알파벳 역순으로 정렬
    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] # 뒤에서부터 출력

6) defaultdict를 이용한 풀이

from collections import defaultdict

def solution(tickets):
    answer = []
    routes = defaultdict(list)
    for ticket in tickets:
        routes[ticket[0]].append(ticket[1])
    for r in routes:
        routes[r].sort(reverse = True)
        
    stack = ["ICN"]
    while len(stack) > 0:
        top = stack[-1]
        if top not in routes or len(routes[top]) == 0:
            answer.append(stack.pop())
        else:
            stack.append(routes[top].pop())
    return answer[::-1]

• 통과한 테스트

  테스트 1
  입력값 〉 [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]
  기댓값 〉 ["ICN", "JFK", "HND", "IAD"]

  테스트 2
  입력값 〉 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL", "SFO"]]
  기댓값 〉 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

  테스트 3
  입력값 〉 [["ICN", "A"], ["A", "B"], ["A", "C"], ["C", "A"], ["B", "D"]]
  기댓값 〉 ["ICN", "A", "C", "A", "B", "D"]

  테스트 4
  입력값 〉 [["ICN", "AAA"], ["ICN", "AAA"], ["ICN", "AAA"], ["AAA", "ICN"], ["AAA", "ICN"]]
  기댓값 〉 ["ICN", "AAA", "ICN", "AAA", "ICN", "AAA"]

  테스트 5
  입력값 〉 [["ICN", "AAA"], ["ICN", "AAA"], ["AAA", "ICN"], ["AAA", "CCC"]]
  기댓값 〉 ["ICN", "AAA", "ICN", "AAA", "CCC"]

  테스트 6
  입력값 〉 [["ICN", "AAA"], ["ICN", "BBB"], ["BBB", "ICN"], ["BBB", "CCC"], ["CCC", "BBB"]]
  기댓값 〉 ["ICN", "BBB", "CCC", "BBB", "ICN", "AAA"]