여행경로

문제

programmers.co.kr/learn/courses/30/lessons/43164#

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

---

풀이

처음엔 단순한 문제인줄 알고 DFS를 사용하지 않고 풀어보려 했다. 내가 생각한 방식은 이러했다.

1. 출발점이 ICN인 것들 추출해서 도착점 알파벳 순으로 앞서는 것은 선택한다.
2. 1에서 선택한 경로의 도착점이 출발점인 것을 골라 알파벳순으로 비교하고 선택하는 과정을 반복한다.

그런데 문제는 위와 같은 방법으로 풀이했을 때 반례가 존재한다는 것이다. 

[["ICN","JFK"],["ICN","ATL"],["JFK","ICN"]]

위의 예시에서 가능한 경로는 ["ICN","JFK","ICN","ATL"]이다. 그러나 내가 생각한 방식을 적용하면 ["ICN","ATL"...이 되어버려서 ticket을 다 사용하지 못한다. 이 문제는 탐색을 하는 DFS와 조건을 검사하는 백트래킹을 같이 사용해야 하는 문제이다. 백트래킹의 constraint는 "모든 티켓을 다 사용할 수 있는 경로"이다.

둘 중에 우선이 되는 것이 모든 티켓을 다 사용해야 한다는 것이다. 다시 말해 알파벳 순으로 앞서는 경로라 해도 모든 티켓을 다 사용할 수 없다면 답이 될 수 없는 것이다.

 

접근 1)

def solution(tickets):
    answer = []
    tickets2 = tickets[:]
    temp = []
    for path in tickets2:
        if path[0] == "ICN":
            temp.append(path)
    # 출발지가 ICN인 것 중에 도착지 기준 알파벳 순으로 정렬
    s_temp = sorted(temp, key = lambda x : x[1])
    start = s_temp[0]
    answer.append(start[0])
    answer.append(start[1])
    # 출발점 정보 tickets2 리스트에서 삭제
    tickets2.remove(start)
    while tickets2:
        temp2 = []
        for path in tickets2:
            if path[0] == start[1]:
                temp2.append(path)
        s_temp2 = sorted(temp2, key = lambda x : x[1])
        # print(s_temp2)
        start = s_temp2[0]
        answer.append(start[1])
        tickets2.remove(start)
    return answer

 

결국 다른 블로그를 참고해 풀었다.(출처는 코드에 기재)

접근 2)

def solution(tickets):
    t = dict()
    for ticket in tickets:
        if ticket[0] in t:
            t[ticket[0]].append(ticket[1])
        else:
            t[ticket[0]] = [ticket[1]]
    print(t)
    for k in t.keys():
        # 알파벳 역순으로 정렬
        t[k].sort(reverse=True)
    print(t)
        
    st = ["ICN"]
    answer = []
    
    while st:
        top = st[-1]
        
        if top not in t or len(t[top]) == 0:
            answer.append(st.pop())
        else:
            st.append(t[top][-1])
            t[top].pop()
        
        print(st)
        
    answer.reverse()
    return answer

# 출처 : https://copy-driven-dev.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-ProgrammersPython-%EC%97%AC%ED%96%89%EA%B2%BD%EB%A1%9C