1. 문제 설명
2. 제한사항
3. 입출력 예
4. 문제 풀이
1) 깊이 우선 탐색(DFS)
- 한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하되, 각 인접 정점을 기준으로 깊이 우선 탐색을 끝낸 후 다음 정점으로 진행
- 스택을 이용하여 어느 정점에서 DFS를 하고 있는지를 기억하고 되돌아감
2) 너비 우선 탐색(BFS)
- 한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하고, 방문한 각 인접 정점을 기준으로 (방문한 순서에 따라) 또 다시 너비 우선 탐색을 행함
- 큐를 이용하여 어느 정점에서 BFS를 해야 하는지를 기록하고 진행함
3) 문제 해결 - DFS 알고리즘 응용
-
스택을 이용하여 재귀적인 "한 붓 그리기" 문제를 해결
- 이것이 가능하다는 것은 문제에서 보장되어 있음
- 재귀적인 성질을 가진 "한 붓 그리기" 문제는 재귀적인 성질을 가진 "그래프의 깊이 우선 탐색"을 응용하여 해결할 수 있음
-
시작 정점은 언제나 "ICN"
-
모든 정점 방문이 아니고, 모든 간선을 거쳐야 함
- 언젠가 한 번 가야 하는데 그 순서를 결정해야 함
-
한 정점에서 택할 수 있는 간선이 두 개 이상인 경우
- 공항 이름의 알파벳 순서를 따름
4) 출발지별 항공권 개수 카운트
from collections import deque
def solution(tickets):
answer = []
stack = deque()
visited = [False] * len(tickets)
tickets.sort() # 출발 공항 이름의 알파벳 기준으로 정렬
# 출발지별 항공권의 개수를 카운트해서 사전으로 만듦
path = {}
for ticket in tickets:
path[ticket[0]] = path.get(ticket[0], 0) + 1
stack.append("ICN")
# stack이 빌 때까지 path에 항공권을 모두 추가
while len(stack) > 0:
pos = stack[-1] # 출발지
next_pos = "ZZZ" # 도착지
# 항공권의 개수가 1이상이면 stack에 삽입하고 방문 표시
if path.get(pos, 0) > 0:
for k in range(len(tickets)):
if visited[k] == False and tickets[k][0] == pos:
# 출발지가 같은 도착지가 여러개이면 알파벳 순서를 따름
if next_pos[0] > tickets[k][1][0]:
next_pos = tickets[k][1]
next_num = k
path[pos] = path.get(pos, 0) - 1
visited[next_num] = True
stack.append(next_pos)
else: # 항공권의 개수가 0이하이면 stack에서 꺼내서 path에 추가
answer.append(stack.pop())
answer.reverse() # path의 역순이 방문하는 공항 경로가 됨
return answer5) 출발지별 도착지들을 인접 리스트로 생성
- 사전을 이용하여 각 공항에서 출발하는 항공권의 리스트를 표현
ICN -> [SFO, ATL]
ATL -> [SFO, ICN]
SFO -> [ATL]
def solution(tickets):
# 사전을 이용하여 각 공항에서 출발하는 항공권의 리스트를 표현
routes = {}
for t in tickets:
routes[t[0]] = routes.get(t[0], []) + [t[1]]
# 알파벳 역순으로 정렬
for r in routes:
routes[r].sort(reverse = True)
stack = ["ICN"]
path = []
while len(stack) > 0:
top = stack[-1]
# 해당 공항에서 출발하는 경우가 없거나 모두 사용한 경우
if top not in routes or len(routes[top]) == 0:
path.append(stack.pop())
else:
stack.append(routes[top][-1]) # 스택에 도착 항공 삽입
routes[top] = routes[top][:-1] # 해당 공항 제외
return path[::-1] # 뒤에서부터 출력6) defaultdict를 이용한 풀이
from collections import defaultdict
def solution(tickets):
answer = []
routes = defaultdict(list)
for ticket in tickets:
routes[ticket[0]].append(ticket[1])
for r in routes:
routes[r].sort(reverse = True)
stack = ["ICN"]
while len(stack) > 0:
top = stack[-1]
if top not in routes or len(routes[top]) == 0:
answer.append(stack.pop())
else:
stack.append(routes[top].pop())
return answer[::-1]-
통과한 테스트
테스트 1
입력값 〉 [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]
기댓값 〉 ["ICN", "JFK", "HND", "IAD"]테스트 2
입력값 〉 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL", "SFO"]]
기댓값 〉 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]테스트 3
입력값 〉 [["ICN", "A"], ["A", "B"], ["A", "C"], ["C", "A"], ["B", "D"]]
기댓값 〉 ["ICN", "A", "C", "A", "B", "D"]테스트 4
입력값 〉 [["ICN", "AAA"], ["ICN", "AAA"], ["ICN", "AAA"], ["AAA", "ICN"], ["AAA", "ICN"]]
기댓값 〉 ["ICN", "AAA", "ICN", "AAA", "ICN", "AAA"]테스트 5
입력값 〉 [["ICN", "AAA"], ["ICN", "AAA"], ["AAA", "ICN"], ["AAA", "CCC"]]
기댓값 〉 ["ICN", "AAA", "ICN", "AAA", "CCC"]테스트 6
입력값 〉 [["ICN", "AAA"], ["ICN", "BBB"], ["BBB", "ICN"], ["BBB", "CCC"], ["CCC", "BBB"]]
기댓값 〉 ["ICN", "BBB", "CCC", "BBB", "ICN", "AAA"]
