📖 문제

📝 풀이 과정1 (틀린 풀이 과정)

1. 티켓 정보를 tickets_dict라는 dictionary 자료형 변수에 담는다. 이때 key는 출발지이고 value는 도착지이다.
   이때 tickets_dict의 value들을 알파벳의 역순으로 정렬한다.
   (이유1. 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return해야하기 때문,
   이유2. list의 요소를 삭제할 때 pop()이 pop(0)보다 시간복잡도상으로 효율적)
2. "ICN"을 출발점으로 DFS를 시작한다.
3. tickets_dict에서 현재 출발지 cur를 key로 가지는 value들 중에서 가장 알파벳순으로 빠른 공항이 다음 도착이 nxt가 된다.
4. 만약 nxt가 마지막 방문지라면,
   4-1. cur에서 갈 수 있는 다른 공항이 있다면 nxt를 그 공항으로 다시 설정한다.
   4-2. cur에서 갈 수 있는 다른 공항이 남아있지 않는다면 경로 끝
5. nxt가 마지막 방문지가 아니라면, nxt를 출발지로 하는 티켓을 찾도록 함수dfs를 재귀호출(3번으로 돌아간다.)

⌨ 코드1 (틀린 코드)

def dfs(cur, tickets_dict, answer):
    answer.append(cur)
    
    nxt = tickets_dict[cur][-1]
    # 마지막 방문지인 경우
    if nxt not in tickets_dict or not tickets_dict[nxt]:
        # 4-1.
        if len(tickets_dict[cur]) != 1:
            nxt = tickets_dict[cur][-2]
            tickets_dict[cur].pop(-2)
        else:
            # 4-2.
            answer.append(nxt)
            return
    else:
        tickets_dict[cur].pop()
    dfs(nxt, tickets_dict, answer)
        
def solution(tickets):
    answer = []
    tickets_dict = dict()
    
    # 티켓 정보 dict 자료형에 넣기 key: 출발지, value: 도착지
    for ticket in tickets:
        if ticket[0] in tickets_dict:
            tickets_dict[ticket[0]].append(ticket[1])
            tickets_dict[ticket[0]].sort(reverse = True)    
        else:
            tickets_dict[ticket[0]] = [ticket[1]]
    
    dfs("ICN", tickets_dict, answer)
    
    return answer

🤔 틀린 이유

다음 예시로 틀린 이유를 설명하려고 한다.

tickets :
[["ICN", "BBB"], ["ICN", "AAA"], ["AAA", "CCC"], ["BBB", "ICN"]]

• 위의 티켓들을 tickets_dict에 담은 것과, 공항끼리 연결된 정보를 그림으로 표시하면 다음과 같다.
  
• 이때 위의 ⌨코드1대로 문제를 푼다면
  
  위 그림과 같이 풀게 되어 answer = ["ICN", "AAA", "CCC"]이 return된다.(옳은 답은 answer = ["ICN", "BBB","ICN", "AAA", "CCC"])

---

📝 풀이 과정2 (정답 풀이 과정)

• dfs를 재귀함수를 이용하는 것 대신, stack을 이용한 풀이

1. 풀이과정1의 1번 과정과 같다. (티켓정보 tickets_dict에 담기)
2. stack에 출발지점인 "ICN"을 넣고 DFS 시작
3. 현재 공항(cur)은 stack의 top이 된다.
   3-1. 만약 cur에서 갈 수 있는 다른 공항이 남아있지 않는다면 경로 끝 -> 정답 리스트에 cur을 추가하고 stack pop
   3-2. 만약 cur에서 갈 수 있는 다른 공항이 있다면, tickets_dict[cur]에서 알파벳순으로 가장 빠른 공항을 stack에 쌓는다.
4. 3번 과정을 stack이 비기 전까지 반복한다.
5. answer를 뒤집는다.
   (stack을 사용해서 마지막 도착지부터 시작해서 정답 리스트 answer에 담아서 현재 answer에는 경로가 역순으로 저장되어 있기 때문)

⌨ 코드2 (정답 코드)

from collections import deque
def solution(tickets):
    answer = []
    tickets_dict = dict()

    # 티켓 정보 dict 자료형에 넣기 key: 출발지, value: 도착지
    for ticket in tickets:
        if ticket[0] in tickets_dict:
            tickets_dict[ticket[0]].append(ticket[1])
            tickets_dict[ticket[0]].sort(reverse = True)    
        else:
            tickets_dict[ticket[0]] = [ticket[1]]

    stack = deque(["ICN"])
    while stack:
        cur = stack[-1]
        if cur not in tickets_dict or not tickets_dict[cur]:
            answer.append(stack.pop())
        else:
            stack.append(tickets_dict[cur].pop())

    answer.reverse()
    return answer

😊 느낀점

dfs, bfs 문제는 기본 코드로 문제를 풀면 웬만한 건 다 풀 수 있다고 생각했는데 이번 기회로 그 생각을 바꾸게 되었다.
문제 조건 "만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다"이 없었다면 level3까지는 아니었을 텐데.. 이 조건 때문에 난이도가 확 올라갔다.
그리고 항상 dfs, bfs 문제를 풀 때 출발지부터 도착지까지 순서대로 경로를 찾아가는 방법만을 고려했는데, 이제는 "도착지"서부터 찾아나가는 방법도 있다는 걸 염두에 두어야겠다.