[Programmers/Kotlin] 여행 경로 (DFS)

[도입]

오랜만에 괜찮다고 생각되는 문제를 만나서 글을 작성하게된다.

문제는 굉장히 간단하다.

출발공항, 도착공항 쌍으로 이루어진 티켓들이 주어지는데, 이 티켓을 모두 사용(이게 이 문제의 핵심이다.)하는 공항경로를 만드는 문제이다.

공항을 정점이라고 했을 때, 보통 정점을 모두 방문하는 문제를 많이 풀어본 사람으로서 (그래서 BFS, DFS 시 정점을 위주로 방문여부를 확인) 좀 당황했었다.

문제에 대한 자세한 내용은 아래를 참고한다.

코딩테스트 연습 - 여행경로

 

 

[잘못된 풀이]

잘못된 풀이의 코드가 날라갔다.. 내가 틀렸던 것은 1, 2 번 테스트 케이스이다.

말로 설명해보자면 

 

 

1. 중복검사(Set<String>)를 경로로 함

  -> 1번테스트 케이스 탈락 (중복되는 경로가 여러번 올 수 있다. ex [["AAA", "BBB"], ["BBB","AAA"], ["AAA", "BBB"]])

2. 모든 항공권(즉 모든 경로)를 사용하는 것이 알파벳순서 지키는 것보다 우선순위임을 간과

  -> 아마 2번 테스트 케이스 탈락 이 부분은 링크의 예시를 참고하면 쉽게 이해할 수 있다.

 

코드에 대한 설명이 없어서 무슨 말인지 전달되지 않았을 것이다. 

아래 정답풀이 사고과정을 보고 다시 잘못된 풀이를 보면 전달이 될 것이다.

 

[정답풀이 사고과정]

기본적으로 DFS 의 로직을 따랐다.

현재 공항에 이어진 

보통 구현하던 DFS 와 차이가 있다면 그래프 만드는 자료구조를 Map<String, ~> 으로 정했다. String 이 정점이 되기 때문이다. 

그리고 1번 테스트케이스를 계속 틀리게 했던 원인이었던 방문 검사는 Set 을 사용하였다.

 

처음에는 원소를

Map<String, LinkedList<String>>, Set<String> 으로 잡아서 경로를 중복검사 해줘서 1번 테스트케이스를 틀렸다.

중복된 경로가 들어올 수 있으니, 경로가 아닌 입력으로 주어진 티켓의 인덱스를 중복검사하는 솔루션을 생각해보았다.

 

Map<String, LinkedList<Pair<String, Int>>>, Set<Int> 로 변경해서 인덱스 중복검사하니 테스트케이스를 통과할 수 있었다. 

 

import java.util.*

class Solution {
    
    val graph = mutableMapOf<String, LinkedList<Pair<String, Int>>>()
    val answer = LinkedList<String>()
    val check = mutableSetOf<Int>()
    var size = 0
    
    fun solution(tickets: Array<Array<String>>): Array<String> {
        size = tickets.size
        
        tickets.forEachIndexed { i, v ->
            val from = v[0]
            val to = v[1]
            graph[from]?.add(Pair(to, i)) ?: run {
                graph[from] = LinkedList(listOf(Pair(to, i)))
            }
        }
        
        graph.forEach { _, v ->
            v.sortBy {
                it.first
            }
        }
        dfs("ICN")
        
        return answer.toTypedArray()
    }
    
    private fun dfs(cur: String): Boolean {
        answer.add(cur)
        println(answer.toString())
        if (answer.size == size + 1) return true
        
        
        val curGraph = graph[cur]
        if (!curGraph.isNullOrEmpty()) {
            for (i in 0 until curGraph.size) {
                val pair = curGraph[i]
                val next = pair.first
                val mappedIdx = pair.second
                
                if (check.contains(mappedIdx)) continue else check.add(mappedIdx) // 중복되는 경로를 가진 티켓이 여러개 나오는 경우 때문
                
                if (dfs(next)) {
                    return true 
                } else {
                    curGraph.add(pair)
                    check.remove(mappedIdx)
                    answer.removeLast()
                }
            }
        }
            
        return false 
    }
    
}