여행경로

https://programmers.co.kr/learn/courses/30/lessons/43164

코딩테스트 연습 - 여행경로

 

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

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

제한사항

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

입출력 예

ticketsreturn

[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]	["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

입출력 예 설명

예제 #1

["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

예제 #2

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

 

문제풀이

 바로 앞에서 풀었던 단어변환과 동일한 문제인줄 알고 풀었더니 

A -> B -> C 

A-> B -> X

뒤가 없는 경우를 선택하지 못하는 코드.....ㅠㅠ 너무 슬프다....

다시 풀자

result = []

def DFS(tickets, visited, L, begin) :
    global result
    #종료조건 : 깊이 다 순회했을 경우 종료
    #print(L)
    if L == len(tickets)+1 :
        return
    #방문한 곳은 결과 배열에 넣음
    if L <= len(tickets) :
        result.append(begin)

    for i in range(len(tickets)) :
        #이미 방문했던 티켓은 재방문 하지 않는다.
        if visited[i] is True : 
            continue
        
        #시작 값이 같은 경우 방문
        if begin == tickets[i][0] :
            visited[i] = True
            #print(i, tickets[i], visited)
            DFS(tickets, visited, L+1, tickets[i][1])
            #print(begin, tickets[i][0], tickets[i][1])
    
def solution(tickets):
    global result
    
    #가능한 경로가 2개 이상인 경우 알파벳 순서가 앞서는 경로 방문을 위해 정렬
    sort_tickets = sorted(tickets, key=lambda x:(x[0], x[1]))
    
    visited = [False for i in range(len(tickets))]
    
    DFS(sort_tickets, visited, 0, "ICN")
    
    #print(result)
    return result

#visited 배열은 tickets개 생성
#시작값은 ICN
#두번째는 반복문 돌면서 [i][0]에 있는것 찾기
#다음 시작값은 [i][1]
#재방문 하지 않게 비지트에 방문한 tickets의 인덱스 저장하기

 

잘 이해안감

def solution(tickets):
    #티켓 오름 차순 정렬
    graph = {}
    
    #1. 그래프 생성
    # { 시작점 - [도착점들] } 쌍의 그래프 생성
    for stackart, end in tickets :
        graph[stackart] = graph.get(stackart, []) + [end]
    print(graph)
    
    #2. 시작점 - [끝점] 역순으로 정렬
    for r in graph.keys() :
        graph[r].sort(reverse=True)
    
    #3. DFS 알고리즘처럼 path를 만들어 줌
    #모든 점을 순회
    stack = ["ICN"]                         #"ICN"을 스택에 먼저 넣습니다.
    path = []
    
    #스택의 꼭대기는 가야 하는 다음 경로는 top을 시작점으로 하는 끝 점들을 
    #역순으로 저장하는 리스트의 가장 마지막 원소
    #스택이 빌때까지 반복
    while stack :
        top = stack[-1]                     #스택에서 가장 위의 저장된 데이터 top을 꺼내옴
        print(top)
        
        #만약 top이 그래프에 없거나, top을 시작점으로 하는 티켓이 없는 경우
        #스택에서 꺼내와 path에 저장
        if top not in graph or len(graph[top]) == 0 :
            path.append(stack.pop())        #스택의 맨 꼭대기에 있는거 빼서 경로에 저장
    
        #더 이상 쌓을 스택이 존재하지 않으면 스택의 top부터 확인하면서
        #dictionary에 스택의 top으로 시작하는 경로가 있는지 확인합니다.
        #top을 시작점으로 하는 끝점 중 가장 마지막 지점을 꺼내와 스택에 저장
        else :
            stack.append(graph[top][-1])
            print(stack)
            graph[top] = graph[top][:-1]
    
    print("최종 : ", path)

    return

#visited 배열은 tickets개 생성
#시작값은 ICN
#두번째는 반복문 돌면서 [i][0]에 있는것 찾기
#다음 시작값은 [i][1]
#재방문 하지 않게 비지트에 방문한 tickets의 인덱스 저장하기

#https://kyoung-jnn.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%ED%8C%8C%EC%9D%B4%EC%8D%ACPython-%EC%97%AC%ED%96%89%EA%B2%BD%EB%A1%9C-DFS-%EC%8A%A4%ED%83%9D
#https://gurumee92.tistory.com/165