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

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

항공편을 모두 이용하여 이동 가능한 여행경로를 탐색해야 하므로 DFS 탐색을 이용하였습니다.

2) 알고리즘

• DFS
• 재귀

3) 풀이 코드

사용 언어 - Python

def solution(tickets: list):
    answer = []                                         # 정답 리스트

    def make_linked(tickets: list):                     # 연결 관계 변수 만드는 함수
        linked = {}                                     # 연결 관계
        visited = {}                                    # 항공편 이용 여부

        for a, b in tickets:                           
            linked[a] = linked.get(a, []) + [b]         # a -> b 연결 추가
            visited[a] = visited.get(a, []) + [0]       # 항공편 방문여부 0으로 초기화
        
        for k in linked.keys():                         # 경로가 여러개인경우 사전순으로 가장 앞에 하나를 출력해야하므로
            linked[k].sort()                            # 도착지를 사전순으로 정렬

        return linked, visited
    
    linked, visited = make_linked(tickets)              # 연결 관계 변수와 방문 여부 변수 생성

    def DFS(routes):                                    # DFS 탐색 (현재까지 경로)
        if answer:                                      # 정답 경로를 찾았다면 종료
            return

        for v in visited.values():                      # 모든 항공편을 이용했는지 확인
            if not min(v):                              # 아직 이용하지 않은 항공편이 있다면 반복문 종료 후 탐색
                break
        else:                                           # 모든 항공편을 이용했다면
            answer.append(routes)                       # 정답에 추가
            return
        
        departure = routes[-1]                                              # 마지막에 도착한곳 = 현재 출발하려는 출발지
        for idx_arrival in range(len(linked.get(departure, []))):           # 출발지에서 이동 가능한 도시들 탐색
            if not visited[departure][idx_arrival]:                         # 이용하지 않은 항공편이라면
                visited[departure][idx_arrival] = 1                         
                DFS(routes + [linked[departure][idx_arrival]])              # 경로에 도착지 추가 하고 다음 경로 탐색
                visited[departure][idx_arrival] = 0

    DFS(['ICN'])                # DFS 탐색

    return answer[0]            # 경로 출력

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

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

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다