문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
모든 공항은 알파벳 대문자 3글자로 이루어집니다.
주어진 공항 수는 3개 이상 10,000개 이하입니다.
tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
주어진 항공권은 모두 사용해야 합니다.
만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
풀이
시도 1.
간단하게 시작이 "ICN" 으로 설정하고 "ICN"에서 시작하는 항공권을 찾아서 sort한 후 알파벳이 빠른 곳을 다시 시작 점으로 정하고 기존의 tickets에서 remove시켜주는 형식의 DFS 알고리즘을 구현 했다. 간단히 하자면,
- ICN에서 갈 수 있는 항공권을 검색.
- 알파벳상 빠른 항공권을 사용.
- 목적지를 새로운 출발지로 설정.
- 사용한 항공권은
remove해줌. tickets을 다 사용할 때 까지 재귀.
answer = ["ICN"]
def dfs(start,tickets) :
temp = []
if len(tickets) == 0 :
return
for i in range (0,len(tickets)):
if tickets[i][0] == start :
temp.append(tickets[i])
temp.sort()
tickets.remove(temp[0])
answer.append(temp[0][1])
dfs(temp[0][1],tickets)
def solution(tickets):
global answer
dfs("ICN",tickets)
return answer이렇게 짰지만 50점이었다.. 무언가 놓친게 있는 것 같다. 1,2번 테스트 케이스가 실패하는 것을 찾아보니 더 이상 갈 수없는 경로가 만들어지면 에러가 나는 것이었다..!🤦♂️ 즉, 알파벳 순으로 하게 된다면 모든 지역을 다 돌지않는 경우가 생길 수 있다..!!!
그래서 가야할 city를 찾아서 모두 돌지 못하면 err가 나기 때문에 이것을 체크 해줘야한다.
-
티켓을 dict에 넣어 도착지를 역순으로 저장.
-
스택을 만들어 순회
- 출발지에 없거나 || 도착지를 다 돌았으면- 스택의 맨위를 답에 넣음.
- 더이상 들어갈 곳이 없다.
-만약 갈 곳이 남았으면
- 스택의 맨 위에 넣는다.
-
반대로 출력.
def solution(tickets):
answer = []
T = dict()
for t in tickets :
if t[0] in T:
T[t[0]].append(t[1])
else:
T[t[0]] = [t[1]]
for i in T.keys():
T[i].sort(reverse = True)
print(T)
st = ["ICN"]
while st:
top = st[-1]
print(top)
if top not in T or len(T[top]) == 0:
answer.append(st.pop())
print("answer",answer)
else:
print("T[top][-1] : ",T[top][-1])
st.append(T[top][-1])
T[top].pop()
answer.reverse()
return answer[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL", "SFO"]]를 입력한다면
{'ICN': ['SFO', 'ATL'], 'SFO': ['ATL'], 'ATL': ['SFO', 'ICN']} 의 딕셔너리를 만든 후
T[top][-1] : ATL
T[top][-1] : ICN
T[top][-1] : SFO
T[top][-1] : ATL
T[top][-1] : SFO을 st에 쌓게 된다. dict에 있는 모든 도시를 탐방 하였기 때문에 차곡차곡 answer에 쌓으면
answer ['SFO']
answer ['SFO', 'ATL']
answer ['SFO', 'ATL', 'SFO']
answer ['SFO', 'ATL', 'SFO', 'ICN']
answer ['SFO', 'ATL', 'SFO', 'ICN', 'ATL']
answer ['SFO', 'ATL', 'SFO', 'ICN', 'ATL', 'ICN']이런 모양으로 쌓는데 stack이기 때문에 역순으로 쌓여서 answer을 제출할 때는 반대로 출력하면 답을 도출할 수 있다.
