문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
- 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
- 주어진 공항 수는 3개 이상 10,000개 이하입니다.
- tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
- 주어진 항공권은 모두 사용해야 합니다.
- 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
- 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
입출력 예
| tickets | return |
| [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]] | ["ICN", "JFK", "HND", "IAD"] |
| [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] | ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] |
입출력 예 설명
예제 #1
["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.
예제 #2
["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.
👩🦰 나의 풀이
from collections import defaultdict
def solution(tickets):
dic = defaultdict(list)
for start, end in tickets:
dic[start].append(end) # key = 출발, value = 도착
def dfs():
stack = ["ICN"]
while stack:
airport = stack[-1]
if airport not in dic or not dic[airport] :
visited.append(stack.pop())
else :
stack.append(dic[airport].pop(0))
visited = list()
for k in dic.keys() :
dic[k].sort() # 값들 오름차순 정렬
dfs()
return visited[::-1]스택을 이용한 dfs 풀이
딕셔너리 값을 내림차순 정렬하고, 뒤에서부터 pop해서 stack에 넣어도 된다.
끝까지 들어가면 visited에 여행경로를 추가하기 시작한다.
[::-1]로 뒤집어준다.
# 제출하면 테케 1, 2 실패
from collections import deque
def bfs(tickets, t, answer):
que = deque()
que.append(t)
while que:
i = que.popleft()
for route in tickets:
if route[0] == i:
que.append(route[1])
answer.append(route[1]) # 목적지 추가
tickets.remove(route)
break
def solution(tickets):
start = "ICN"
answer = [start]
tickets.sort(key=lambda x: x[1]) # 목적지를 기준으로 오름차순준으로 오름차순
bfs(tickets, start, answer)
return answer
bfs로 구현
제한사항 "만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다."를 위해 sort로 정렬.
tickets의 출발지 값과 que에서 뽑은 원소가 같으면 que와 answer에 티켓의 목적지를 넣는다.
쓴 티켓은 삭제하고 break한다.
이 코드의 문제점은 출발지가 ICN인 티켓이 여러개 일 때 무조건 목적지의 알파벳이 앞서는 것부터 방문한다는 것.
이렇게 하면 항공권을 모두 사용한다는 보장이 없다.
ex) [["ICN", "AAA"], ["ICN", "BBB"], ["BBB", "ICN"]]
["ICN", "BBB"]부터 가야 모두 방문 가능.
이 문제는 dfs로 푸는게 더 적절하다.
😶 다른 사람 풀이
# 출처 : https://wwlee94.github.io/category/algorithm/bfs-dfs/travel-route/
from collections import defaultdict
def solution(tickets) :
# 특정 타켓의 인접 리스트를 구하는 함수
def init_graph() :
routes=defaultdict(list) # 리스트를 딕셔너리로 변환
for key, value in tickets :
routes[key].append(value)
return routes
# 스택을 사용한 DFS
def dfs() :
stack=["ICN"]
path=[] # 가려고하는 경로를 저장하는 변수
while len(stack) > 0 : # stack이 비어있을 때까지
top=stack[-1] # 맨 마지막 값
# 특정 공항에서 출발하는 표가 없다면 또는 있지만 티켓을 다 써버린 경우
if top not in routes or len(routes[top]) == 0 :
path.append(stack.pop())
else :
stack.append(routes[top].pop(0))
return path[::-1] # 거꾸로 뒤집기
routes=init_graph()
for r in routes :
routes[r].sort() # 키 r의 값을 오름차순으로 정렬
answer=dfs()
return answer
init_graph함수는 리스트를 딕셔너리로 변환한다.
스택을 사용해서 DFS를 구현한다.
티켓에 출발지 top이 없거나 딕셔너리에 값이 없으면(이미 방문해서 목적지가 없음) dfs는 끝까지 들어감.
스택의 맨 끝에 있는 값을 뽑아서 경로 path에 추가한다.
왔던 길을 다시 돌아가며 반복한다. 길이 있으면 또 더 깊이 들어간다.
😊 유용한 코드
defaultdict(default_factory)전에 한 번 본 적 있는 함수.
default_factory에 타입을 넣어준다.
😊 좋았던 부분
routes[r].sort()딕셔너리의 key로 값들을 정렬
# 출처 : https://wwlee94.github.io/category/algorithm/bfs-dfs/travel-route/
from collections import defaultdict
def solution(tickets):
# 특정 타켓의 인접 리스트를 구하는 함수
def init_graph() :
routes=defaultdict(list)
for key, value in tickets :
routes[key].append(value)
return routes
# 재귀 호출을 사용한 DFS
def dfs(key, footprint) :
if len(footprint) == N+1 :
return footprint
# 출발지에서 갈 수 있는 공항들 가기
for idx, country in enumerate(routes[key]) :
routes[key].pop(idx)
fp=footprint[:] # deepcopy
fp.append(country)
ret=dfs(country, fp) # 그 다음 경로 탐색
if ret : return ret # 모든 티켓을 사용해 통과한 경우
routes[key].insert(idx, country) # 통과 못했으면 티켓 반환
routes=init_graph()
for r in routes :
routes[r].sort()
N=len(tickets)
answer=dfs("ICN", ["ICN"])
return answer
재귀호출을 사용한 dfs
여행경로 footprint가 항공권의 갯수와 같으면 여행경로 반환
footprint를 fp에 복사하는 작업을 하지 않으면 항공권을 모두 사용하지 않는 잘못된 경로를 담을 수 있다.
# 출처 : https://velog.io/@eunseokim/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-DFSBFS-%EC%97%AC%ED%96%89-%EA%B2%BD%EB%A1%9C
from collections import defaultdict
def solution(tickets):
tdict=defaultdict(list)
# 딕셔너리 생성
for start, end in sorted(tickets) : # 알파벳 순으로 방문하므로 정렬
tdict[start].append(end)
answer = []
def dfs(node) :
if not tdict[node] : # 딕셔너리에 값이 없으면
return node
while tdict[node] :
next=tdict[node].pop(0)
answer.append(dfs(next))
return node # 현재 노드에서 갈 수 있는 경로가 없으면
dfs("ICN")
answer.append("ICN")
return answer[::-1]
재귀호출을 이용한 dfs 풀이
// https://tosuccess.tistory.com/36
import java.util.*;
class Solution{
boolean[] visited;
ArrayList<String> answers;
public String[] solution(String[][] tickets){
visited=new boolean[tickets.length];
answers=new ArrayList<String>();
int count=0;
dfs(count, "ICN", "ICN", tickets);
Collections.sort(answers);
String[] answer=answers.get(0).split(" ");
return answer;
}
public void dfs(int count, String present, String answer, String[][] tickets){
if(count == tickets.length){
answers.add(answer);
return;
}
for(int i=0; i< tickets.length; i++){
if(!visited[i] && tickets[i][0].equals(present)){
visited[i]=true;
dfs(count+1, tickets[i][1], answer+" "+tickets[i][1], tickets);
visited[i]=false;
}
}
return;
}
}
dfs 구현
리스트 answers에 여행 경로가 담긴 문자열 answer을 추가한다.
가능한 여행 경로의 모든 경우가 리스트answers에 담긴다.
answers를 정렬하면 {{"ICN ATL ICN SFO ATL SFO"}, {"ICN ATL SFO ATL ICN SFO"}, {"ICN SFO ATL ICN ATL SFO"}}
get으로 알파벳 순서가 가장 앞서는 0번째 값 {"ICN ATL ICN SFO ATL SFO"}을 가져온 뒤, 공백을 기준으로 나눈 문자열을 answer에 저장하고 반환한다.
문제 출처 💁♀️ 프로그래머스
'coding test' 카테고리의 다른 글
| [파이썬] 등굣길 (0) | 2021.04.18 |
|---|---|
| [파이썬, Java] 입국심사 (0) | 2021.04.17 |
| [파이썬] 이중우선순위큐 (0) | 2021.04.16 |
| [파이썬, Java] 가장 먼 노드 (0) | 2021.04.07 |
| [파이썬] 정수 삼각형 (0) | 2021.04.06 |