[프로그래머스/파이썬] DFS/BFS 여행경로

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

---

알고리즘 분류

• DFS

문제풀이

틀린코드
def solution(tickets):
from collections import deque

key_list=[]
graph={i[0]:[] for i in tickets}
for i in tickets:
    graph[i[0]].append(i[1])
    key_list.append(i[0])

result=["ICN"]
queue=deque()
queue.append("ICN")

while queue:
    check=False
    now=queue.popleft()
    graph[now].sort()
    if len(graph[now])==0:
        break
    for i in range(len(graph[now])):
        k=0
        if graph[now][i] in key_list:
            k=i
            check=True
            break

    pick=graph[now].pop(k)
    result.append(pick)
    if check:
        queue.append(pick)

return(result)

처음에 BFS로 접근했다가 75%만 맞았다.
테스트케이스1은 [['ICN','B'],['B','ICN'],['ICN','A'],['A','D'],['D','A']]에서 결과값은 ['ICN', 'A', 'D', 'A']가 아니라 ['ICN', 'B', 'ICN', 'A', 'D', 'A']가 나와야 한다.
BFS로 접근하니 알파벳 순서가 앞서는 경우로 진행을 쭉 해버리는데 그렇게 되면 주어진 항공권을 모두 사용해야 하는 조건에 안 맞게 된다.

우선 graph={'ICN': ['B', 'A'], 'B': ['ICN'], 'A': ['D'], 'D': ['A']}로 만들어주고 stack을 활용하기 때문에 오름차순으로 정렬한다.(그래야 B,A에서 A부터 뽑음)

top 현재 공항에서 출발하는 항공권 자체가 없거나 이미 사용해서 더이상 없는 경우 result에 stack의 pop()한 값을 넣어준다.
그렇지 않은 경우 stack에 top에 해당하는 도착 공항 값을 넣어준다.

소스코드

def solution(tickets):
    graph={i[0]:[] for i in tickets}
    for i in tickets:
        graph[i[0]].append(i[1])
        
    for i in graph.keys():
        graph[i].sort(reverse=True)
    
    result=[]
    stack=["ICN"]
    while stack:
        top=stack[-1]
        
        if top not in graph or len(graph[top])==0:
            result.append(stack.pop())
        else:
            stack.append(graph[top].pop())
    
    result.reverse()
    return result