01. 이해
인천에서 출발해 모든 항공권을 이용하는 여행 경로를 짜야 함
같은 출발지를 가진 경로가 2개 이상일 경우 도착지가 알파벳 순으로 앞선 경로를 선택 한다.
02. 계획
일단 출발지가 인천인 티켓 중 도착지가 알파벳순으로 앞선 경로의 티켓을 찾는다.
여기가 출발지.
이후로는 현재 도착지를 출발지로 가지는 티켓들을 차례로 탐색해서 알파벳 순으로 앞선 티켓을
찾아나가면 될듯.
03. 실행
fun solution(tickets: Array<Array<String>>): Array<String> {
val result = mutableListOf<String>()
val temp = mutableListOf<String>()
val visitList = MutableList(tickets.size) { false }
tickets.sortBy { it[1] }
dfs("ICN", tickets, visitList, temp, result, 0)
return result.toTypedArray()
}
fun dfs(currentCity : String,
tickets: Array<Array<String>>,
visitList: MutableList<Boolean>,
temp : MutableList<String>,
result : MutableList<String>,
count : Int) : Boolean {
temp.add(currentCity)
if (count == tickets.size){
result.clear()
result.addAll(temp)
return true
}
(tickets.indices).forEachIndexed { index, i ->
if (tickets[index][0] == currentCity && !visitList[index]){
visitList[index] = true
if (dfs(tickets[i][1], tickets, visitList, temp, result, count + 1))
return true
visitList[index] = false
}
}
temp.removeAt(temp.size-1)
return false
}
04. 회고
dfs, bfs 개념이 잘 이해되지 않은 상태에서 풀려니까 어려움이 많았다.
일반적인 dfs 방식을 적용하면 프로그래머스의 네가지 테스트 케이스 중 두 가지가 풀리지 않는데
동일한 티켓이 존재할 수 있으며 알파벳 순만 따라가는 것이 최적의 코드가 되지 않을 수도 있기
때문이다.
예) 1->2, 1->3, 3->2
라는 티켓이 있었을 때 1에서 갈 수 있는 도착지가 2, 3이 있으니까 당연히 알파벳 순으로 2를 가게
되는데 이렇게 되면 거기서 더 여정이 이어질 수 없다.
모든 경유지를 방문하기 위해서는 1->3->2의 순으로 가야하는 것.
그러기 위해서는 일단 알파벳 순으로 가다가 갈 수 있는 곳 까지 갔는데 전 경로를 가지 못했다면
그 앞의 경로로 돌아가 다음 최선의 경우를 찾아가야 하는 것이다.
예시를 예로 들자면 1->2를 간 다음에 2에서 갈 수 있는 곳이 없는데 아직 1->3을 쓰지 않았으므로
다시 1로 돌아와 2가 아닌 3을 선택하고 3->2로 진행해야 하는 것.
갑자기 다음주에 코테가 잡혀서 급하게 자료구조가 적용된 문제들을 풀려고 하니까 너무 어렵다 ㅠ
