문제
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한 사항
- 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
- 주어진 공항 수는 3개 이상 10,000개 이하입니다.
- tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
- 주어진 항공권은 모두 사용해야 합니다.
- 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
- 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
문제를 보고 든 생각
풀 수 있을 것 같았다.
다른 조건 없이 그냥 이어진대로 쭉 출력하게끔 만들면 되지 않을까라는 생각을 했다.
그래서 별다른 생각 없이 구현을 시작했다.
나의 아이디어
이어진대로 답안 리스트에 공항들을 담는다.
대신 출발지가 같은 티켓이 있다면 도착지를 고를 때 문자열순으로 골라야 하므로 인풋 리스트를 도착지순으로 정렬한 후에 dfs/bfs 함수를 구현한다.
그리고 for문을 이용해서 공항들을 함수 안에 매개변수로 하나씩 집어넣으며 함수를 실행시킨다.
결과
def solution(tickets):
temp = []
visited = [False for _ in range(len(tickets))]
plan = []
for index, ticket in enumerate(tickets):
if ticket[0] == "ICN":
temp.append(ticket)
ticket.append(index)
tickets = sorted(tickets, key=lambda x : x[1])
temp = sorted(temp, key=lambda x : x[1])
def airline(tickets, itinery, visited):
visited[itinery[2]] = True
for ticket in tickets:
if not visited[ticket[2]] and itinery[1] == ticket[0]:
plan.append(ticket[1])
airline(tickets, ticket, visited)
for index, ticket in enumerate(tickets):
if ticket not in visited:
if index == 0:
plan.append(temp[0][0])
plan.append(temp[0][1])
airline(tickets, temp[0], visited)
else:
airline(tickets, ticket, visited)
return plan총 4개의 테스트 케이스 중 2개에서 정답 처리를 받고 2개에서 오답 처리를 받았다.
제출을 하면서도 모든 케이스에서 정답 처리가 될 것 같지는 않았다.
그 이유는 내가 구현하지 못한 부분을 코드 작성 중 발견했기 때문이었다.
그 부분을 발견했다면 구현을 하고 제출을 하는 게 당연하지만 그대로 제출을 해봤던 이유는 당최 어떻게 구현을 해야하는지 감이 안 와서였다.
내가 구현하지 못한 부분은 아래에서 설명하려고 한다.
티켓이 총 4장 있다고 하자.
["ICN", "AAA"], ["AAA", "BBB"], ["AAA", "CCC"], ["CCC", "AAA"]
내가 위에 작성해놓은 코드에 이 input을 넣는다면 결과는
["ICN", "AAA", "BBB"]가 나오게 된다.
하지만 답은
["ICN", "AAA", "CCC", "AAA", "BBB"]가 되어야 한다.
즉, 한 경로로 향했을 때 모든 티켓을 사용하지 못하게 되는 경우 다시 돌아오도록 만들어야 했다.
하지만 이미 탐색해버린 공항은 visited로 방문 체크를 했기 때문에 다시 돌아갈 수도 없는 노릇이고
그렇다고 방문 체크를 안 하자니 무한 루프에 빠지게 될 수도 있다.
그래서 저 부분을 결국 포기하고 제출을 했던 것이다.
2일 동안 고민을 해봤지만 묘안이 떠오르지가 않았다.
검색을 통해 알게 된 내용
나는 그래프 탐색 문제를 풀면서 단 한번도 인풋으로 들어온 그래프 데이터를 변형시켜본 적이 없다.
항상 그 자체로 있어야만 혹은 그 자체로 유지되어 있어도 문제가 해결됐기 때문이다.
하지만 이 문제는 달랐다.
해시테이블 구조로 인풋으로 들어온 데이터를 변형시킨다는 게 참 새로웠다.
ICN을 가장 먼저 탐색할 수 있도록 하기 위해 따로 리스트도 만들고 조건문도 써붙이고 했는데
해시테이블 구조로 데이터를 저장하니 코드가 훨씬 간결했다. 그래서 이해하기도 쉬웠다.
이해하기 쉬웠던 만큼 아쉬움도 컸다.
왜 이런 생각을 못했을까 하는 아쉬움이었다.
검색을 통해 알게 된 풀이
routes = {}
# 출발지를 key로 도착지를 value로
for ticket in tickets:
routes[ticket[0]] = routes.get(ticket[0], []) + [ticket[1]]
# 사전순 배열은 reverse로
# pop을 사용할 것이기 때문에
for r in routes:
routes[r].sort(reverse=True)
stack = ["ICN"]
path = []
while stack:
# 현재 출발지를 now에 저장
now = stack[-1]
# now에 저장된 출발지가 원래부터 key로 존재하지 않았거나
# now에 저장된 출발지로부터 더이상 갈 수 있는 도착지가 없다면
if now not in routes or len(routes[now]) == 0:
# 여행 경로 리스트에 집어 넣는다.
# (여행 경로의 마지막 장소임을 의미)
path.append(stack.pop())
# now에 저장된 출발지로부터 갈 수 있는 도착지가 있다면
else:
# stack에 now로 갈 수 있는 도착지를 저장한다.
stack.append(routes[now].pop())
# 코드상 먼저 path 배열에 들어가게 되는 장소는
# 마지막 여행 경로이기 때문에
# 답으로 반환해줄 때는 리스트를 뒤집어서 반환해주어야 한다.
answer = path[::-1]
print(answer)느낀 점
이렇게 dfs를 사용할 수 있다는 걸 배울 수 있었다.
현재까지의 경험으로 미루어봤을 때, bfs보다 dfs가 더 응용의 폭이 넓은 느낌이 든다.
그리고 dfs를 써야할지 bfs를 써야할지 헷갈릴 때, 이 문제가 한 붓 그리기인지 아닌지 확인해보자.
만약 한 붓 그리기라면, dfs로 풀면 효율적일 것이다!