코딩 테스트 연습 - 여행경로(프로그래머스 레벨3)

versatile309·2020년 3월 18일
0

CodingTest

목록 보기
10/24

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로 진행해야 하는 것.
갑자기 다음주에 코테가 잡혀서 급하게 자료구조가 적용된 문제들을 풀려고 하니까 너무 어렵다 ㅠ

0개의 댓글