프로그래머스[programmers] - 여행경로(Kotlin)[LV3]

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

 

문제 풀이

평소와 같이 DFS/BFS로 생각을 하고 풀었지만, 평범한 DFS/BFS 문제는 아니었다.

테스트케이스에서 주는 혼란을 주는 것도 있었다.

 

테스크케이스를 예로 들어서 설명해보겠다.

[ ICN, SFO] , [ICN, ATL] , [SFO, ATL] , [ATL, ICN], [ATL, SFO]라는 티켓이 있다.

0번 index -> 1번 index로의 값은 항공권으로 갈 수 있다는 뜻이다.

여기서 생각해야 볼 것은 경로가 여러 개라면 알파벳 순서로 앞서는 것이 정답이기 때문에 알파벳 순서로 정렬을 해줘야 한다.

val list = tickets.sortedBy{it[1]}

1번째 index가 도착지점이기 때문에 도착지점을 알파벳 순서로 정렬을 해줬다.

 

탐색은 DFS를 사용했다.

 

재귀의 조건은 재귀의 깊이가 tickets의 깊이와 같다면, 즉 모든 티켓을 사용할 경우이다.

 

해당 티켓을 이미 사용했는지, 안 했는지를 검사하기 위해서 boolean 배열이 필요하다.

반복문은 티켓의 개수만큼 반복하고, 사용하지 않은 티켓 중에서 출발지점이 현재 재귀의 출발지점과 동일한 지역과 같아야 한다.

for(i in 0 until tickets.size){
    if(!visited[i] && tickets[i][0] == cur){
        visited[i] = true
        dfs(tickets[i][1], cnt+1, tickets, visited)   
        if(!isFinished){
            result.removeLast()
            visited[i]=false                    
        }
    }            
}

 

dfs로 갈 수 있는 항공권을 모두 검사했지만, 티켓을 모두 사용하지 못했다면 해당 순서에서 티켓의 사용은 올바르지 않다는 뜻이므로,

경로의 마지막 값을 제거하고, 티켓의 사용을 취소한다.

 

문제의 특이한 점은 모든 지점을 방문했냐가 아닌 티켓을 모두 사용했는가라는 점이었다.

실제로 A->B->C를 모두 방문했더라도, 티켓을 모두 사용하지 않았다면 해당 경로는 적절하지 않다는 점이었고,

이 점이 해당 문제의 차별점이자 어려운 점이었던 것 같다.

 

전체 코드

class Solution {
     
    val result = mutableListOf<String>()
    var isFinished = false
    fun solution(tickets: Array<Array<String>>): Array<String> {
        val visited = Array(tickets.size){false}
        var start = "ICN"
        val list = tickets.sortedBy{it[1]}
        dfs(start,0,list,visited)      
        return result.toTypedArray()
    }
    
    fun dfs(cur: String, cnt:  Int,tickets:List<Array<String>>, visited:Array<Boolean>){
        if(cnt==tickets.size){ //다 뽑았을때
            isFinished = true
        }
        result.add(cur)        
        for(i in 0 until tickets.size){
            if(!visited[i] && tickets[i][0] == cur){
                visited[i] = true
                dfs(tickets[i][1], cnt+1, tickets, visited)   
                if(!isFinished){
                    result.removeLast()
                    visited[i]=false                    
                }
            }            
        }        
    }
}