[프로그래머스 코딩 테스트 연습] BFS/DFS 4. 여행경로

BFS/DFS

4. 여행경로 

---

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 

항상 ICN 공항에서 출발합니다.

나는 stack을 이용해서 푸는 코드를 참고 했다. 그래서 항상 stack은 stack = ["ICN"] 으로 초기화

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

 

 

제한사항

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

  • 출발지는 같고 도착지가 다른 경우가 있을 수 있기 때문에 출발지를 key로, 도착지들을 리스트에 담아 저장하는 딕셔너리 형태로 티켓들을 우선 정리해 줍니다.

• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

  • 모든 티켓이 소진되어야 합니다.

테스트 케이스 

# test case 1
print(solution([["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]))
# ["ICN", "JFK", "HND", "IAD"]

# test case 2
print(solution([["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]))
# ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

---

솔루션 소스코드 

def solution(tickets):
    answer = []
    ticket_graph = dict()
    # [출발지] : [도착지 리스트] 로 티켓 정리
    for ticket in tickets:
        if (ticket[0] in ticket_graph):
            ticket_graph[ticket[0]].append(ticket[1])
        else:
            ticket_graph[ticket[0]] = [ticket[1]]
    
    for starting_point in ticket_graph:
        # 역순으로 저장하는 이유: ticket_graph[starting_point]의 value인
        # [destination list]이 reverse 된 상태에서 pop을 해야 알파벳 순으로 도착지 선택 가능 
        # ex) 'SFO' : ['SFO','ATL'] -pop()-> 'SFO' : ['SFO'] , pop 된 값 = 'ATL'
        ticket_graph[starting_point].sort(reverse=True)
    stack = ["ICN"]
    # stack이 빌때까지 반복 
    while stack:
        # stack top 저장 
        top = stack[-1]
        if top not in ticket_graph or len(ticket_graph[top]) == 0:
            # top이 출발지인 티켓이 없거나 top이 출발지인 티겟이 모두 소진된 경우 
            # answer에 stack을top부터 pop해주면서 역순으로 값을 넣음 
            answer.append(stack.pop())
        else:
            # 우선 stack에 값을 넣어주고, 티켓이 모두 소진되면 stack에서 값을 pop하면서 answer에 넣어주는 것!
            # top을 출발지로 하는 도착지 리스트에서 알파벳이 가장 우선되는 도착지를 pop해서 append
            # append된 값이 새로운 stack top이 될 것임
            stack.append(ticket_graph[top].pop())
    answer.reverse()

    return answer

• tickets를 { starting point : [destinations list], ... } 딕셔너리 형태로 다음과 예시와 같이 정리합니다. 

# test case 1
{'ICN': ['JFK'], 'HND': ['IAD'], 'JFK': ['HND']}

# test case 2
{'ICN': ['SFO', 'ATL'], 'SFO': ['ATL'], 'ATL': ['SFO', 'ICN']}

• 이때, value인 도착지 배열을 reverse 해서 알파벳 역순으로 정렬해주는 이유는 해당하는 key 값의 배열에서 pop 해서 가장 마지막에 저장된 값을 가져오는데 이때 알파벳이 가장 앞 순서인 도착지를 가져와야 하기 때문입니다. 
• stack은 방문하는 도시를 순서대로 저장하는 배열인데 항상 인천 공항을 출발점으로 하기 때문에 stack=["ICN"]으로 초기화해줍니다. 

else:
	stack.append(ticket_graph[top].pop())

• 그리고 else 부분을 먼저 봅시다.
  • 현재 방문한 도시를 나타내는 stack top 값을 출발지 (key)로 하는 도착지들의 리스트에 접근하여 pop 해줍니다. 
  • 즉, pop 한 값은 현재 도시에서 가지고 있는 티켓으로 갈 수 있는 도착지 중 알파벳이 가장 앞순서인 도착지를 pop 한 값이기 때문에 다음 방문지라고 생각하시면 됩니다.
  • 다음 방문지가 정해졌으므로 이 값을 방문한 도착지를 저장하는 배열인 stack에 append해 줍니다. 
  • 그러면 else가 끝나고 while 처음 부분으로 다시 돌아가 현재 방문한 도시가 다시 stack top으로 설정되어 해당 값을 key로 하는 도착지들의 리스트에 다시 접근하고 위와 같은 과정이 반복되는 것입니다. 

if top not in ticket_graph or len(ticket_graph[top]) == 0:
            answer.append(stack.pop())

• stack에 방문할 도시들을 저장하다가 현재 방문한 도시를 출발지로 하는 티켓이 없거나 남아있는 티켓이 없어 도착지 리스트의 길이가 0 인 경우는 if 문에 걸리게 됩니다. 
  
  • else문 처리 과정을 거치다가 더 이상 도착지 리스트에 남아 있는 티켓이 없는 경우 이제 그 값은 answer로 가져옵니다. 
  • 또는 해당 값을 출발지로 하는 티켓이 없는 경우에도 그 값을 answer로 가져옵니다. 
• answer에 담긴 값을 다음 예시와 같이 거꾸로되어 있습니다. 

# test case 1
['IAD', 'HND', 'JFK', 'ICN']

# test case 2
['SFO', 'ATL', 'SFO', 'ICN', 'ATL', 'ICN']

• 그래서 reverse해서 출력해주어야 합니다. 

---

References

• copy-driven-dev.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-ProgrammersPython-%EC%97%AC%ED%96%89%EA%B2%BD%EB%A1%9C