문제
https://school.programmers.co.kr/learn/courses/30/lessons/43164
- tickets 배열의 모든 여행 경로를 조합해서 전체 여행 경로를 만드려고 한다.
: tickets 배열에는 ["출발지", "도착지"] 형태로 배열이 저장되어있다. - 갈 수 있는 경로가 여러 개인 경우 알파벳 순서가 앞선 도시부터 방문한다.
- 주어진 항공권은 모두 이용한다.
- 위 방법으로 작성한 최종 여행 경로를 answer 배열로 리턴해라.
풀이
- 문제를 처음 보았을 때, 딕셔너리를 생성해 {"출발지": [도착지 배열]} 형태로 tickets 배열에 담긴 정보를 저장하였다. 딕셔너리를 활용해 [출발지, 도착지] 정보를 queue에 append, pop 하며 BFS 알고리즘을 구현하려고 했다.
- 하지만 코드를 구현하는 과정에서 여러 문제가 발생했고, 블로그를 서치하면서 잘못 생각했던 부분들을 파악했다.
본 문제를 풀면서 놓쳤던 부분들을 아래에 정리하였다.
💡 문제를 풀면서 놓쳤던 부분들
- 출발지는 항상 "ICN" 공항이다.
- 방문했던 도시를 재방문 가능하다.
: 다른 DFS, BFS 문제들을 풀다 보면 방문한 지역은 재방문하지 못하는 경우가 많기 때문에 이번 문제도 자연스럽게 동일하게 생각했다. 하지만 본 문제는 출발지가 동일한 티켓이 여러 개 존재할 수 있으므로, 방문했던 지역을 재방문하는 것은 문제가 되지 않는다.
💡아이디어
문제 풀이
- 위 게시글에 본 문제에 대한 아이디어 및 원리가 깔끔하고 이해하기 쉽게 정리되어 있다.
코드
코드 1) 아래 코드를 더욱 효율적으로 작성한 코드
참고한 블로그
위 블로그를 참고하여 코드를 작성했다.
알게된 점
- 딕셔너리의 get() 메소드
def solution(tickets):
answer = []
# 1. 그래프 생성
routes = dict()
for (start, end) in tickets:
routes[start] = routes.get(start, []) + [end]
# start를 키로 가지는 value(해당 출발지의 도착지)에 새로운 도착지점을 더해서 routes 딕셔너리의 start 키 값을 가지는 value에 저장 (=새로운 도착지점 찾을 시 value값 갱신)
# 여기서 (start, [])의 []는 만약 아직 start 값이 딕셔너리에 없는 경우 빈 리스트에 해당 도착지를 더해서 딕셔너리를 갱신하는 것이다.
# 2. {시작점: [끝점]} 딕셔너리 생성 및 끝점을 역순으로 정렬
for r in routes.keys():
routes[r].sort(reverse = True)
# 3. DFS 알고리즘으로 path를 만들어준다
stack = ["ICN"]
path = []
while stack:
top = stack[-1]
if top in routes and len(routes[top]) > 0:
stack.append(routes[top][-1])
routes[top] = routes[top][:-1] # stack에 넣어준 마지막 요소를 routes 딕셔너리에서 뺌
else:
path.append(stack.pop()) # 현재 출발지점의 도착지가 없으면 stack의 정보를 path에 저장함
# 4. 만든 path를 거꾸로 answer 배열에 저장
answer = path[::-1]
return answer코드 2) 처음에 구현한 코드
def solution(tickets):
# {"출발지: 도착지"} 딕셔너리 생성 => 딕셔너리 명: hash
hash = {}
for i in range(len(tickets)):
hash[tickets[i][0]] = 0
for key in hash.keys():
arr = []
for i in range(len(tickets)):
if key == tickets[i][0]:
arr.append(tickets[i][1])
arr.sort()
hash[key] = arr
# DFS
stack = ["ICN"] # 항상 "ICN" 공항에서 출발함
path = [] # 최종 여행 경로 저장
while stack:
now = stack[-1]
if now not in hash or len(hash[now]) == 0:
path.append(stack.pop()) # 더 이상 갈 경로가 존재하지 않으면 해당 위치를 path 배열에 추가함
else:
stack.append(hash[now][0]) # 이동할 도시를 stack에 추가
hash[now] = hash[now][1:] # 방문한 도시를 빼고 저장
answer = []
for i in range(len(path)): # path에는 여행지 이동 경로의 역순으로 저장되어 있으므로 path 배열의 역순을 answer 배열에 저장함
answer.append(path[len(path)-i-1])
# answer = path[::-1] # 위 for문에서 실행한 배열 역순으로 저장과 동일한 코드
return answer실행 결과
- 참고한 블로그 의 코드는 전체 테스트 케이스를 0.02ms 안에 모두 실행 가능하다. 위 글을 참고하여 코드를 더욱 효율적으로 수정할 예정이다.
+오류
본 문제를 다시 풀어보면서 DFS 구현 시 while문 안의 조건문의 순서를 바꿔서 코드를 작성했다. 이 경우 다음과 같은 오류가 발생한다. 해당 원인을 파악하는 중이다.
def solution(tickets):
answer = []
# 출발지, 목적지 정보 딕셔너리 생성
route = {}
for i in range(len(tickets)):
route[tickets[i][0]] = 0
for key in route.keys():
arr = []
for i in range(len(tickets)):
if key == tickets[i][0]:
arr.append(tickets[i][1])
arr.sort()
route[key] = arr
# DFS
stack = []
stack.append("ICN")
path = []
while stack:
now = stack[-1]
# 오류 발생 부분
if len(route[now]) > 0 and now in route: # 이동할 도시가 있는 경우, 해당 도시를 stack에 추가하고 딕셔너리의 value 값에서 이동한 도시를 빼줌
stack.append(route[now][0])
route[now] = route[now][1:]
else: # 이동할 도시가 없는 경우
path.append(stack.pop()) # 최종 경로 저장 배열에 도시를 저장함
answer = path[::-1]
return answer실행 결과
👩🏻💻 AI를 좋아하는 IT학부생