여행경로

it 취업을 위한 알고리즘 문제 풀이

문제

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

[

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

[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

programmers.co.kr

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

코드

from collections import defaultdict
cnt = 0
ticketSize = 0
destination = ""
answer  = []
res  = []

# tickets = [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"], ["ICN","AAA"],["AAA","BBB"],["IAD","ICN"]]

'''
ICN:[(AAA,0),(JFK,0)] 
JFK:[(HND,0)]
HND:[(IAD,0)]
IAD:[(ICN,0)]
AAA:[(BBB)]
'''
## 재귀를 사용한 DFS
def dfs(routes, start, moveCnt):
    global res
    global answer
    global ticketSize
    if moveCnt == ticketSize - 1:
        for elemToVal in routes[start]:
            if elemToVal[1] == 0:
                elemToVal[1] = 1
                answer.append(elemToVal[0])
                res = answer[:] #리스트값 복사
                return answer
    else:
        for elemToVal in routes[start]:
            if elemToVal[1] == 0:
                elemToVal[1] = 1 #방문 체크
                answer.append(elemToVal[0])
                dfs(routes,elemToVal[0],moveCnt+1)
                elemToVal[1] = 0 #방문체크 해제
                answer.pop()


def solution(tickets):
    global ticketSize 
    global res
    ticketSize = len(tickets) # 6
    # 해쉬 딕셔너리로 tickets 정보 인접 리스트 그래프로 표현
    routes = defaultdict(list)
    for fromKey, toValue in tickets: 
        routes[fromKey].append([toValue,0])

    for rKey in routes:
        routes[rKey].sort()


    answer.append("ICN")
    dfs(routes,"ICN",0)

    return res

문제해결방법

• 출발점 key로 하고 도착점을 list value로 하는 딕셔너리로 그래프를 구현했다. list value에서 도착점에 다시 티켓 사용여부를 표시하여 그래프 탐색에서 방문한 곳은 다시 방문하지 않도록 했다.
  • {출발나라 :[[도착나라, 티켓 사용 유무],[도착나라, 티켓 사용 유무]]}
• 항상 최초 출발지점은 "ICN"이므로 answer 리스트에 값을 추가하고 DFS 탐색을 진행했다. 출발지점 key로 도착지점의 정보를 뽑아서 해당 도착지점이 방문하지 않았다면 방문처리를 해주고 경로에 추가하고 도착 vertex로 이동한다. 다시 이전에 도착 vertex를 출발 vertex로 다음 도착 vertex를 위와 같은 방법으로 탐색을 진행한다.
• 이렇게 탐색을 진행하면서 이동 카운트를 하나씩 증가하고, 이동카운트가 (티켓숫자-1)이 되었을 때 최종 도착 점을 경로에 추가하면서 그래프 탐색을 종료한다.
  • 이동카운트를 처음에 0으로 시작했기 때문에 마지막 도착점을 추가하는 지점도 이동카운트가 (티켓숫자-1)일 때 해주도록 했다.
    • 그리고 잘못된 경로로 진입했을 때를 대비해 재귀 함수가 리턴되면 방금 추가했던 도착점을 경로에서 제거하도록 하고 다음 경로를 탐색할 수 있도록 코드를 구현했다.
    • 잘못된 경로라하면 티켓수를 모두 사용하지 않고 최종 도착지점으로 도달했을 경우이다. (최종 도착 지점은 출발 티켓의 지점이 없는 곳)