ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 프로그래머스 - 여행 경로
    알고리즘 문제 풀이 2021. 1. 17. 00:46
    /*
     * 2021-01-17
     * https://programmers.co.kr/learn/courses/30/lessons/43164?language=kotlin
     */
    
    fun travelRoute(tickets: Array<Array<String>>): Array<String> {
    
      // route 를 맵으로 생성
      val routeMap = mutableMapOf<String, Route>()
      tickets.forEach {
        val start = it[0]
        val dest = it[1]
        val routeString = "$start-$dest"
        val route = routeMap[routeString]
        if (route == null) {
          routeMap[routeString] = Route(start, dest, 0, emptyList(), 1)
        } else {
          route.count = route.count + 1
        }
      }
    
      // 모든 route 에 dest 로 시작하는 route 를 다음 route 로 추가
      tickets.forEach { ticket ->
        val start = ticket[0]
        val dest = ticket[1]
        val routeString = "$start-$dest"
    
        routeMap[routeString]?.nextRoutes = routeMap.filter {
          it.value.start == dest
        }.map { it.value }
      }
    
      // route 탐색
      return routeMap.map { (airport, route) ->
        if (airport.startsWith("ICN")) {
          // 모든 route visited 를 false 로 초기화
          routeMap.values.forEach { it.visitedCount = 0 }
          searchRoute(route, tickets.count(), mutableListOf(route.start))
        } else {
          emptyArray()
        }
      }.filter { it.isNotEmpty() }
        .minByOrNull { it.joinToString() } ?: emptyArray()
    }
    
    fun searchRoute(node: Route, target: Int, history: MutableList<String>): Array<String> {
      node.visitedCount = node.visitedCount + 1
      val nextRoutes = node.nextRoutes
      var result: Array<String> = arrayOf()
    
      nextRoutes.sortedByDescending { it.dest }.forEach {
        if (it.visitedCount < it.count) {
          val start = it.start
          // history 복사
          val newHistory = history.map { h -> h }.toMutableList()
          newHistory.add(start)
    
          if (history.count() != target) {
            searchRoute(it, target, newHistory).let { searchResult ->
              if (searchResult.isNotEmpty()) {
                result = searchResult
              }
            }
            // 백트래킹
            it.visitedCount = it.visitedCount - 1
          }
        }
      }
    
      if (history.count() == target) {
        history.add(node.dest)
        result = history.toTypedArray()
      }
      return result
    }
    
    data class Route(
      val start: String,
      val dest: String,
      var visitedCount: Int,
      var nextRoutes: List<Route>,
      var count: Int
    ) {
      override fun toString(): String {
        return "$start-$dest"
      }
    }

    dfs 를 이용해서 풀다가 막혀서 좀 찾아보니 백트래킹을 이용하면 풀 수 있는 문제였다.
    백트래킹을 좀 더 공부해야겠다..

    반응형

    댓글 0

Designed by Tistory.