leetcode 332 Level hard - python

leetcode 풀이 참조
leetcode 332

• 초기 코드

from typing import List

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        start_list = list()
        tickets = sorted(tickets, key=lambda x: x[1])
        for tic in tickets:
            if tic[0] == "JFK" and tic[1] in [x[0] for x in tickets]:
                for t in tic:
                    start_list.append(t)
                tickets.remove(tic)
                break
            elif tic[0] == "JFK" and len(tickets) == 1:
                return tickets[0]
        count = len(tickets)
        while count > 0:
            temp_list = list()
            for i in tickets:
                if start_list[-1] == i[0] and i[1] in [x[0] for x in tickets]:
                    temp_list.append(i)
                    start_list.append(temp_list[0][1])
                    tickets.remove(i)
                    count -= 1
                    break
                elif count == 1:
                    start_list.append(i[1])
                    count -= 1

        return start_list

a = Solution()
# print(a.findItinerary([["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]))
# print(a.findItinerary([["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]))
print(a.findItinerary([["EZE","TIA"],["EZE","HBA"],["AXA","TIA"],["JFK","AXA"],["ANU","JFK"],["ADL","ANU"],\
                       ["TIA","AUA"],["ANU","AUA"],["ADL","EZE"],["ADL","EZE"],["EZE","ADL"],["AXA","EZE"],\
                       ["AUA","AXA"],["JFK","AXA"],["AXA","AUA"],["AUA","ADL"],["ANU","EZE"],["TIA","ADL"],\
                       ["EZE","ANU"],["AUA","ANU"]]))

코드를 보면 뭔가 복잡하다는 것을 느낄 수 있다.

tickets = sorted(tickets, key=lambda x: x[1])

처음 시작하는 문자 "JFK" 가 같을 경우 다음 문자열의 어휘 순서를 보기 때문에
x[1] 기준으로 sort 하여 주었다.
그 후 이어지는 문자를 찾고 찾았지만 결국 길고 중간에 끊기는 부분이 있는 문제가 들어오면
실패...한다.
아래는 DFS 방식으로 풀이한 방법이다

import collections

class Solution:
	def findItinerary(self, tickets: List[List[str]]) -> List[str]:
    	tic = collections.defaultdict(list)
        
        for key, val in sorted(tickets, reverse=True):
        	tic[key].append(val)
        result = list()
        def dfs(val):
        	while tic[val]:
            	dfs(tic[val].pop())
            result.append(val)
        dfs("JFK")
        
        return result[::-1]

collections 를 import 하여 defaultdict(list) 를 만들어 초기 다음 목적지를 초기화 해주며,
출발지가 같은 항목을 key로 하여 defaultdict를 생성한다.

tic[key].append(val)

sorted -> reverse 이유는 밑에 설명하겠다.

def dfs(val):
	while tic[val]:
		dfs(tic[val].pop())
	result.append(val)
dfs("JFK")

sort 한 이유는 문제에서 출발지가 같으면 글자 순서로 정렬하라고 하여 정렬하였으며, pop(0)를 하면 효율이 굉장히 떨어지기 때문에 pop() 을 사용하기 위해서 reverse=True로 tic을 정렬한 것이다.

재귀함수를 거치며 마지막 결과부터 append 될 것이기 때문에

return result[::-1]

DFS, BFS 떠올리고 구현하는게 아직은 너무 힘들지만 머리 박다보니 좀... ㅎ

• 포인트

1. DFS 생각하여 재귀로 잘 구현하기