[프로그래머스] 여행경로

# 문제 설명

주어진 항공권 티겟들을 모두 이용하여, 방문하는 공항 경로를 반환해라. 첫 공항은 항상 "ICN"에서 출발한다.

모든 항공은 알파벳 대문자 3글자로 이루어지며, 만일 가능한 경로가 2개 이상이라면 알파벳 순서가 앞서는 경로를 반환한다.

항공권 티겟 정보 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 것을 의미한다.

 

# 입출력 예시

입력	출력
[["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"]

 

# 코드 풀이

def solution(tickets):
    n = len(tickets)
    answer = []
    def dfs(s, path, nexts):
        if len(path) > n: # 티켓소진하면
            answer.append(path)
            return
        
        avail = [b for a,b in nexts if a==s] # 시작이 같은 티겟들
        if not avail:
            return
        for d in sorted(avail):
            path.append(d) # 맨처음에 현재노드 방문 안하고, 다음노드를 방문
            nexts.remove([s, d])
            dfs(d, path[:], nexts[:])
            
            path.pop()
            nexts.append([s, d])
            
    dfs("ICN", ["ICN"], tickets)
    return answer[0] # 알파벳 순서가 앞서는 것을 반환

 

# 핵심 포인트

- 현재 항공에서 다음으로 갈 항공을 고르는 경우이므로, DFS 그래프 알고리즘을 푼다.

- 거쳐온 경로 path와 남은 티겟들 nexts는 반드시 값을 복사하여 탐색해야 한다.

- for문에서 재귀호출로 다른 경로를 탐색해나가는 경우에는, 이전 선택에 영향을 받지 않도록 해야한다.