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

공부한 자료

https://daebaq27.tistory.com/82

https://veggie-garden.tistory.com/42

[Python] DFS & BFS

https://veggie-garden.tistory.com/42

---

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

프로그래머스

---

풀이 코드

from collections import deque

def solution(tickets):
    # 주어진 항공권은 모두 사용
    # 주어진 공항수 꽤 많음
    tickets.sort()
    dic = {}
    for tic in tickets:
        if tuple(tic) not in dic.keys():
            dic[tuple(tic)] = 1
        else:
            dic[tuple(tic)] +=1

    for root in [x for x in tickets if x[0]=="ICN"]:
        deq = deque()
        deq.append([root]) #dic, visited list
        while deq:
            visited = deq.popleft() #현재 다루는 dic과 그것이 사용된 횟수
            for tic in tickets:
                if (visited[-1][1] == tic[0]) and (visited.count(tic) < dic[tuple(tic)]):
                    if len(visited)+1 == len(tickets):
                        mod = [x[1] for x in visited+[tic]]
                        mod.insert(0, visited[0][0])
                        # print(mod)
                        return mod
                    else:
                        deq.append(visited+[tic])


    return #방문하는 공항 경로 #알파벳 순서가 앞서는 경로

• 알파벳 정렬은, 처음부터 input 리스트 'tickets'을 sort시키고 시작하면 해결된다.
• DFS의 특이한 버전이었다. 
  
  - input에 동일한 티켓이 여러 장 포함될 가능성이 있다. 따라서 다음 탐색 노드를 추가할 때 visited 존재 여부로 결정해서는 안 된다. (이미 방문하여 visited에 존재하지만, 탐색 가능한 것이 여전히 남아 있을 수 있다)
     ✂︎ 미리 counter dictionary를 생성하고, visited가 포함하는 개수와 비교해야 한다:
          visited.count(tic) < dic[tuple(tic)]
  
  - 지금까지 경로 데이터를 모두 가지고 있어야 한다
     ✂︎ deque의 원소 자체를 visited 리스트로 저장
     ✂︎ deep 하게 for문 돌 때, 기존 visited에 현재 탐색 원소를 append하여 기존 visited의 몸뚱아리를 키우는 것이 아니다.
         별도의 리스트(visited + [tic])로 만들어 그것을 deque에 append한다.
         (효율성 괜찮나..? 싶었으나 더 간단한 방법이 떠오르지 않음)
  
  
• 리스트를 원소로 가지는 리스트의 처리는 Unhashable error에 주의해야 한다. 나는 dictionary 생성 및 count를 위해 각 리스트 원소를 tuple로 변환하였다.
  https://daewonyoon.tistory.com/363 

[Python] 리스트를 딕셔너리의 키로 사용하려 하는데 에러가 발생한다. TypeError: unhashable type

 

• 트리 형태로 시각화한 후 수도코드 짜는 게 훨씬 수월할 듯.