[코딩테스트 python] 방향이 있는 그래프 순환 구조(DFS)

 

프로그래머스

> 프로그래머스의 여행경로 문제

 

처음에 enumerate 활용했지만
그 경로가 아닌 경우 돌아가는 루트가 없어서 실패

프로그래머스 문제 풀이 여행 경로

이분이 설명해주신 예시보고 차근차근 이해하면서 DFS로 다시 작성
(코드는 위의 게시글 참고!)

1. 출발-도착 형태로 경로 정리
2. 알파벳 순으로 리스트 정렬(스택구조 > 역순)
3. dfs로 모든 티켓 다 사용하는 경로 찾기
   
   • point : 방문한 경로 체크하는 리스트와 정답 리스트는 별도 관리
   • 방문한 경로 체크하는 리스트의
     [ 0번 = 가장 먼저 넣은 도시]
     [ -1번 = 가장 마지막에 넣은 도시]
   • 방문한 경로 체크하는 리스트를 역순으로 정답에 저장
      == 거슬러 올라가면서 갈림길이 있는 지 check
   • 갈림길이 있어서 남은 경로를 방문 안 했다면 해당 top에서 남은 경로 방문

def dfs(routes, start, answer):
    path = []
    path.append(start) # 출발점 입력
    
    while path: # len(path)==0란 의미
            # 	>> answer에 모든 도시 저장 완료
            # 	>> 즉, 모든 도시에 남김없이 방문완료
            
        top = path[-1] # path에 가장 최근에 넣은 도시(도착점) ==> 출발점
        print(path, top)
        
        # top not in routes >> only도착만 하는 단방향의 경우
        # len(routes[top])==0
        # 	 >> routes[top](출발)의 도착점이 하나도 없을 때 = 모든 도착점 방문 완료
        if top not in routes or len(routes[top])==0:
            print('if:', routes)
            answer.append(path.pop()) #가장 마지막에 도착해야할 도시가 0번으로 저장됨
            print('if:', answer)   
        else:
            path.append(routes[top][-1])
            routes[top] = routes[top][:-1]
    
    return answer[::-1] 

def solution(tickets):
    #경로 정리
    routes = {}
    for (departure,arrival) in tickets:
        routes[departure] = routes.get(departure, [])+[arrival]
        routes[departure].sort(reverse=True)
            # pop은 가장 마지막에 넣은 data 추출하기때문에
            # 먼저 방문해야하는 도시를 최근 == 역순정렬
    
    answer = []
    return dfs(routes, "ICN", answer) #dfs함수 호출

다른 분 풀이 확인하니, routes를 정리할 때 

from collections import defaultdict

사용하는 방법도 있음

 

---

예시

#input 
tickets = [["ICN", "AAA"], ["ICN", "CCC"], ["CCC", "DDD"], ["AAA", "BBB"], ["AAA", "BBB"], ["DDD", "ICN"], ["BBB", "AAA"]]

['ICN'] ICN
['ICN', 'AAA'] AAA
['ICN', 'AAA', 'BBB'] BBB
['ICN', 'AAA', 'BBB', 'AAA'] AAA
['ICN', 'AAA', 'BBB', 'AAA', 'BBB'] BBB
# 'BBB': [] == 처음 알파벳순으로 방문한 AAA의 루트 종료
# 그래서 역순으로 거슬로 올라가면서 모든 도시를 방문 했는 지 확인

                                                        #top인 'BBB': [] 방문완료 
if: {'ICN': ['CCC'], 'CCC': ['DDD'], 'AAA': [], 'DDD': ['ICN'], 'BBB': []} 
if: ['BBB']
['ICN', 'AAA', 'BBB', 'AAA'] AAA  #top인 'AAA': [] 방문완료 
if: {'ICN': ['CCC'], 'CCC': ['DDD'], 'AAA': [], 'DDD': ['ICN'], 'BBB': []}
if: ['BBB', 'AAA']
['ICN', 'AAA', 'BBB'] BBB                               #top인 'BBB': [] 방문완료 
if: {'ICN': ['CCC'], 'CCC': ['DDD'], 'AAA': [], 'DDD': ['ICN'], 'BBB': []}
if: ['BBB', 'AAA', 'BBB']
['ICN', 'AAA'] AAA            #top인 'AAA': [] 방문완료 
if: {'ICN': ['CCC'], 'CCC': ['DDD'], 'AAA': [], 'DDD': ['ICN'], 'BBB': []}
if: ['BBB', 'AAA', 'BBB', 'AAA']
['ICN'] ICN

# 엇 그런데,
# top인 'ICN': ['CCC']에 방문 안 한 도시가 남아있음
#    즉, 알파벳 순으로 먼저 방문했던 'AAA'의 경로가 아니라는 뜻
#        그래서 'CCC'로 다시 방문함

['ICN', 'CCC'] CCC	
['ICN', 'CCC', 'DDD'] DDD
['ICN', 'CCC', 'DDD', 'ICN'] ICN
#top인 'ICN': [] 방문완료 
if: {'ICN': [], 'CCC': [], 'AAA': [], 'DDD': [], 'BBB': []}
if: ['BBB', 'AAA', 'BBB', 'AAA', 'ICN']
['ICN', 'CCC', 'DDD'] DDD      #top인 'DDD': [] 방문완료 
if: {'ICN': [], 'CCC': [], 'AAA': [], 'DDD': [], 'BBB': []}
if: ['BBB', 'AAA', 'BBB', 'AAA', 'ICN', 'DDD']
['ICN', 'CCC'] CCC
         #top인 'CCC': [] 방문완료 
if: {'ICN': [], 'CCC': [], 'AAA': [], 'DDD': [], 'BBB': []}
if: ['BBB', 'AAA', 'BBB', 'AAA', 'ICN', 'DDD', 'CCC']
['ICN'] ICN
#top인 'ICN': [] 방문완료
if: {'ICN': [], 'CCC': [], 'AAA': [], 'DDD': [], 'BBB': []}
if: ['BBB', 'AAA', 'BBB', 'AAA', 'ICN', 'DDD', 'CCC', 'ICN'] #역순 저장

#마지막
path = []  # >> while문 종료

 

>> 이 문제는 모든 tickets을 다 사용할 수 있는 경로를 찾는 문제이기 때문에
     즉, 방향이 있는 그래프 순환 구조

중간에 끊기는 부분
['ICN'] ICN
routes:  {'ICN': ['CCC'] ...
여기서 다른 루트를 방문 해도, 앞서 저장한 루트와 자연스럽게 순환

 >> ["DDD", "ICN"]가 있어서 'DDD', 'ICN', 'AAA'로 이어짐