📃 문제
프로그래머스 여행경로
알고리즘 - DFS, Stack
DFS 재귀 호출이 아닌 stack을 이용하여 깊이우선탐색
조건
- 주어진 공항 수는 3개 이상 10,000개 이하입니다.
-> 조합X - tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
-> [a,b]와 [b,a]는 다르다. - 주어진 항공권은 모두 사용해야 합니다.
-> 모든 항공권 다 이용했을 때가 return 조건 - 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
- 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
💡 풀이 과정
1) DFS 재귀 이용🤯
visited 전달에 문제가 있었음
import copy
def solution(tickets):
answer = 'Z '*10000
routes = {}
for ticket in tickets:
if ticket[0] not in routes:
routes[ticket[0]] = []
routes[ticket[0]].append(ticket[1])
fromlist = list(routes.keys()) #['ICN', 'SFO', 'ATL']
visited = []
result = ['ICN']
def dfsroute(now, visited, result):
nonlocal answer
if now not in fromlist:
return
if len(visited) == len(tickets):
if ''.join(result)<answer:
answer = ' '.join(result)
return
cnt = 0
for to in routes[now]:
print(now, to, visited)
if (now, to) not in visited:
visited.append((now, to))
result.append(to)
visited2 = copy.deepcopy(visited)
dfsroute(to, visited2, result)
else: cnt+=1
if cnt== len(routes[now]):
return
dfsroute('ICN', visited, result)
return list(answer.split())재귀가 return 되어 그다음 for to in route[now]가 작동할때 갖고있는 visited에 문제가 있었음. deepcopy이용해봤으나 해결되진 못함.
2) stack을 이용한 DFS🥳
-
Idea :
stack을 이용하여 끝항공편(다음 연결이 없는)이 아닌 항공편은 쌓아두고 뒤부터 pop아이디어 :
스택을 이용하자
1. 스택 맨처음은 ICN
2. 스택이 비지 않는 동안 반복
3. now = 스택 가장 마지막값
3-1. now에서 출발하는 편이 있으면 result에 routes[now][-1]저장하고 stack.append(routes[now].pop()) (그출발편그래프에서ㅃ짐)) // 그럼 result ICN ATL. stack [ATL]
3-2 now에서 출발하는 편이 없으면 if not routes[now]: 끝테스트케이스 1,2 오답
그래서 찾은 반례입력 : [["ICN", "A"], ["A", "B"], ["A", "C"], ["C", "A"], ["B", "D"]]
기댓값 : ["ICN", "A", "C", "A", "B", "D"]
이처럼 ICN-A-B-D로 연결되버린다면 모든 항공편 이용조건을 만족시키지 못한다
최종 아이디어
아이디어 수정 :
1. 스택, result(반환할정답배열)은 ['ICN']
2. 스택이 비지 않는 동안 반복
3. now = 스택 가장 마지막값
- > pop하지 않는다! 위의 반례 참고, 연결편 없는 공항 만날때 까지 계속 routes에서만 없애가며 스택에 담아두어야 한다.
3-1. now에서 출발하는 편이 없다면, 스택마지막값(now인 셈)을 pop하여 result에 담는다.
3-2. now에서 출발하는 편이 있다면, routes에서만 없애가며 스택에 담는다.
4. 맨 마지막에 도착할 공항부터 담기는 셈이기 때문에 역순으로 반환해야한다.
def solution(tickets):
# {'ICN' : ['SFO', 'ATL']}꼴로 입력받기
routes = {}
for ticket in tickets:
if ticket[0] not in routes:
routes[ticket[0]] = []
routes[ticket[0]].append(ticket[1])
# pop()으로 맨 뒷요소를 제거하여 result에 삽입하려면 맨 뒷요소가 알파벳이 빨라야한다 : 내림차순!
for route in routes:
routes[route] = sorted(routes[route], reverse=True)
result, stack = ['ICN'], ['ICN']
while stack:
now = stack[-1]
if now not in routes or not routes[now] : # 3-1
result.append(stack.pop())
else: # 3-2
stack.append(routes[now].pop())
# 역순 반환
return result[::-1][:-1]
# //now = ATL //3-1 후에 re ICN ATL ICN. stack [ICN]
# // now ICN // 또 다시 re ICN ATL INC SFO stack [SFO]
# // now SFO// re ICN ATL ICN SFO ATL. stack [ATL] #SFO끝남
# // now ATL // re ICN ATL ICN SFO ATL SFO. stack [SFO] # ATL끝남
# // now SFO인데 routes['SFO'] =[] 비었음
🔍 정리 & 배운 것
딕셔너리 선언 defaultdict
from collection import defaultdict
dic = defaultdict(list) # value값이 빈배열인 딕셔너리로 선언!!
print(dic['k1']) # [] 배열 역순
# print(result[:0:-1]) # 맨처음 넣은 ICN 제외 나머지의 역방향
# print(result[::-1][:-1]) #
# 정순 배열
print(result)
# ['ICN', 'D', 'B', 'A', 'C', 'A', 'ICN']
print(result[::-1])
# ['ICN', 'A', 'C', 'A', 'B', 'D', 'ICN']
print(result[-1::-1])
# ['ICN', 'A', 'C', 'A', 'B', 'D', 'ICN']
print(result[-2::-1])
# ['A', 'C', 'A', 'B', 'D', 'ICN']
print(result[1::-1])
# ['D', 'ICN']
# 맨처음 넣은 ICN 제외 나머지의 역방향
print(result[:0:-1])
# ['ICN', 'A', 'C', 'A', 'B', 'D']
# 맨처음 넣은 ICN 제외 나머지의 역방향
print(result[::-1][:-1])
# ['ICN', 'A', 'C', 'A', 'B', 'D']
