-Today's Learning Content-
- 여행경로 알고리즘 풀이
1. 오늘의 알고리즘 풀이
내용 정리
오늘은 항공권 문제를 풀어본 경험을 공유해보려고 한다.
문제는 주어진 항공권 정보를 바탕으로 여행 경로를 계산하는 것이다.
항상 "ICN" 공항에서 출발하며, 가능한 경로가 여러 개일 경우 알파벳 순서대로 경로를 선택해야 한다.
하지만 코드 작성 후 몇 가지 테스트 케이스에서 실패가 발생했다.
이 글에서는 문제를 분석하고 내가 작성한 코드의 문제점을 짚어보며, 어떻게 수정할 수 있을지에 대해 이야기해보겠다.
1) 📊 문제 분석
주어진 문제는 기본적으로 그래프 탐색 문제다. 각 공항을 노드로, 항공권을 간선으로 보고, 출발점인 "ICN"에서 시작하여 가능한 모든 경로를 찾아야 한다.
경로가 여러 가지일 때는 알파벳 순서대로 경로를 선택해야 한다. 또한, 모든 항공권을 한 번씩만 사용해야 한다는 조건이 있다.
예시
tickets = [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL", "SFO"]]이 경우, "ICN"에서 출발하여 모든 항공권을 사용한 경로는 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]여야 한다.
2) 📝 코드 풀이
처음에는 깊이 우선 탐색(DFS)을 이용해서 문제를 풀었다.
import Foundation
/*
1. 항상 ICN 공항에서 출발
2. 방문 순서는 알파벳 순
3. 주어진 항공권은 모두 사용할 것
*/
func solution(_ tickets:[[String]]) -> [String] {
var answer: [String] = []
var ticketDic: Dictionary<String, [String]> = [:]
// 모든 티켓 정보를 입력(알파벳 순)
for ticket in tickets {
let departure = ticket[0]
let destination = ticket[1]
ticketDic[departure, default: []].append(destination)
ticketDic[departure]?.sort()
}
func dfs(_ travelDestination: String) {
answer.append(travelDestination) // 여행 경로 저장
// 다음 여행지가 없으면 return
guard let destination = ticketDic[travelDestination]?.first else { return }
ticketDic[travelDestination]?.removeFirst() // 티켓 삭제
dfs(destination) // 다음 행선지로 이동
}
dfs("ICN")
return answer
}
print(solution([["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]))
// 출력: ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]코드 설명
- 알파벳 순으로 티켓을 처리:
ticketDic[departure]?.sort()를 통해 각 공항에서 갈 수 있는 목적지들을 알파벳 순으로 정렬하고, 그 중 첫 번째를 선택하는 방식으로 경로를 탐색했다.
- DFS를 이용한 탐색:
dfs함수에서 현재 공항에서 갈 수 있는 첫 번째 목적지를 선택한 후, 그 목적지로 이동하면서 티켓을 하나씩 사용해 나갔다.- 여행 경로가 완성되면 이를
answer에 추가하고, 더 이상 갈 곳이 없으면 종료된다.
이렇게 하면 문제가 없을 것이라고 생각하고 프로그래머스에 제출했다.
결과는...
두 개의 테스트 케이스가 실패하여 통과하지 못했다.
혹시 주석 등이 문제가 될 수도 있으니 지우고 다시 시도해보아도 결과는 똑같았다.
그렇다면 내가 작성한 코드에 문제가 있었다는건데... 그게 무엇일까?
3) 🚨 코드의 문제점
1️⃣ 최적 경로를 찾지 못함
- 경로가 여러 개 있을 때 첫 번째 경로만 탐색하고 종료되기 때문에, 모든 경로를 탐색하지 못한다. 예를 들어,
["ICN", "ATL", "ICN", "SFO"]와 같은 경로를 찾지 못한다.
2️⃣ 모든 티켓을 사용하지 않음
- 티켓을 하나씩 사용하고, 그 후 더 이상 갈 곳이 없다면 즉시 종료된다. 하지만 이 방식은 특정 경로에서 모든 티켓을 사용하지 못했을 때, 다른 경로를 시도할 기회를 주지 않기 때문에 실패한다.
4) ♻️ 피드백과 개선점
내 코드에서 발생한 문제는 모든 경로를 탐색하지 않고, 첫 번째 경로만 탐색하는 방식에서 발생했다.
그래서 아래와 같은 개선점을 적용하기로 했다.
1️⃣ 모든 가능한 경로를 탐색:
- 각 공항에서 갈 수 있는 모든 경로를 시도해야 한다. 따라서 단순히 첫 번째 경로만 선택하는 것이 아니라, 여러 경로를 시도해야 한다.
2️⃣ 백트래킹(Backtracking) 기법 사용:
- 경로를 탐색할 때 한 경로가 실패하면 다른 경로로 돌아가서 시도할 수 있도록, 백트래킹 방식을 적용해야 한다. 만약 경로가 잘못되었으면 돌아가서 다른 경로를 선택할 수 있도록 해야 한다.
5) 🔥 개선된 코드 풀이
이제 위의 문제를 해결할 수 있도록 코드를 수정해보았다.
가장 중요한 점은 모든 경로를 시도하고, 백트래킹을 사용하여 경로를 복원하는 것이다. 아래는 개선된 코드다.
func solution(_ tickets:[[String]]) -> [String] {
var answer: [String] = []
var ticketDic: Dictionary<String, [(to: String, check: Bool)]> = [:]
// 모든 티켓 정보를 입력(알파벳 순)
for ticket in tickets {
let departure = ticket[0]
let destination = ticket[1]
// 티켓의 도착지 정보에 도시 이름과 여행 여부(Bool)를 삽입
ticketDic[departure, default: []].append((destination, false))
// 티켓의 도착지 도시 이름순으로 정렬
ticketDic[departure]?.sort(by: { $0.to < $1.to })
}
func dfs(_ travelDestination: String) {
answer.append(travelDestination) // 여행 경로 저장
// 티켓이 존재하지 않으면 return
guard ticketDic[travelDestination] != nil else { return }
// 모든 도시를 여행하도록 반복
for (index, (next, check)) in ticketDic[travelDestination]!.enumerated() {
// 다녀왔던 도시인지 확인
guard !check else { continue }
// 이미 모든 도시를 다녀왔는지 확인
guard answer.count != (tickets.count + 1) else { return }
// 이번 도시를 다녀왔다고 체크
ticketDic[travelDestination]![index].check = true
// 다음 도시로 출발
dfs(next)
}
}
// 모든 도시를 여행하는 방법 탐색 시작
dfs("ICN")
return answer
}6) 🤔 결론
이번 문제에서 중요한 점은 백트래킹을 통해 모든 경로를 시도할 수 있도록 하는 것이었다. 또한, 단순히 첫 번째 경로만 탐색하는 것이 아니라, 모든 가능한 경로를 시도해보고, 실패하면 다시 돌아가서 다른 경로를 시도해야 한다.
이 방식으로 코드를 수정하면 주어진 모든 조건을 만족하는 경로를 정확하게 찾을 수 있다.
코드를 작성하는 과정에서 알고리즘의 제약 조건을 충분히 고려하지 않으면, 문제를 해결하는 데 큰 어려움이 있을 수 있다는 점을 다시 한 번 깨달았다.
그런데...
또 실패했다ㅎㅎ
-Today's Lesson Review-
오늘은 내게 부족하다고 생각한 알고리즘과 자료구조에 대해 공부했다.
특히 DFS에 대해 공부하며 이와 관련된 알고리즘을 푸는데 시간을 썼는데,
생각대로 잘 되지 않았다...
이론상 완벽하다고 생각하는데 왜 안되는지 모르겠다.