[프로그래머스 고득점 Kit] 여행 경로(DFS, 스택, BFS)

[프로그래머스 고득점 Kit] 여행 경로

문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

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

제한사항
모든 공항은 알파벳 대문자 3글자로 이루어집니다.
주어진 공항 수는 3개 이상 10,000개 이하입니다.
tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
주어진 항공권은 모두 사용해야 합니다.
만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

 

입출력 예 설명
예제 #1
["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

예제 #2
["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

 

 

 

---

[내 풀이]

# 런타임 에러
# 알파벳 순서라는 것만 보고, 알파벳 순으로 하면 당연히 가능한 경로일 것이라 착각

- 다시 푼 내 풀이. 스택을 연습하기 위해서 스택을 이용해서 풀이했다.

#모든 도시를 방문할 수 없는 경우는 없다
#주어진 항공권은 모두 사용해야 한다
#이 두가지 조건덕에 stk에서 pop되는 게 무조건 answer 도착지 마지막 부분이라는 것을 확신 가능

from collections import defaultdict
def solution(tickets):
    answer = []
    t_dict = defaultdict(list)
    
    #{출발지:[도착지들]}
    for ticket in tickets:
        t_dict[ticket[0]].append(ticket[1])
    
    for key in t_dict.keys():
        t_dict[key].sort(reverse=True)
        
    stk = ['ICN']
    while stk:
        now = stk[-1]
        if now not in t_dict or len(t_dict[now])==0:
            answer.append(stk.pop())
        else:
            stk.append(t_dict[now].pop())
    return answer[::-1]

 

---

[대표 풀이]

- now=path[-1] 의 활용, 가능하다면 이렇게 결과 리스트를 그대로 활용하는 것이 직관적이고 헷갈리지 않는다. 

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"])

 

---

[대표 풀이]

- defaultdict(list) : 기본 value값이 빈 리스트인 딕셔너리 생성

- 정렬을 반대로 해서 pop: 이 분의 짬이 느껴짐. 이렇게 할 경우 일일이 맨 처음 값부터 index 값을 지정해가면서 돌 필요가 없어지기 때문이다. 그냥 맨 마지막 것을 인덱스 지정 없이 빼내는 것이 깔끔하다.

- if now not in t_dict : 딕셔너리도 not in을 쓸 수 있다. key 기준

- stack에 들어가는 것: 체크해야 되는 값들. 모든 값들이 stack에 들어갔다 나와야함

- 그리고 원하는 값 answer 에 해당하는 것은 순서가 있어서, 그 조건을 만족하는 것은 그 때마다 바로 나오는 것이어야 함. 여기서는 맨 마지막에 도착한 값을 특정할 수 있다. 더 이상 나아갈 데가 없다는 것으로. 그러니  

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]

 

---

[대표 풀이]

- 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 answer