[프로그래머스] 여행 경로

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

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

주어진 (출발지,도착지) 쌍으로 이루어진 배열들을 모두 순회하였을 때 방문 순서를 반환하는 그런 문제이다. 

 

A에서 B,C로 갈 수 있는 상황이라면 우선 B로 이동하고, 그 다음 B에서 갈 수 있는 곳으로 가고.... 그 다음 갈 길이 없으면 C에서 갈 수 있는 곳으로 가고...

 

느낌이 오는가?

 

DFS(깊이 우선 탐색)을 활용해아 하는 문제이다. 

 

DFS를 위해서는 하나의 스택과 하나의 큐가 필요했다. 그리고 방문했는지 여부를 파악할 Bool 타입의 배열 또한 필요하다. 

 

우선 구현 순서를 나열해보자. 

---

1. 조건에 맞게 도착지 기준으로 tickets를 오름차순 정렬해준다. 

2. 모든 노선을 사용해야 한다. 즉 배열의 모슨 원소들을 사용하여 visited 배열을 채워야 한다. 

3. visited는 tickets의 길이 + 1 이어야 한다. 즉 모두 다 방문하여 돌았다는 것을 의미한다. 

4. 방문 순서는 깊이 우선 탐색(DFS)과 같다. 

---

자세한 순서는 코드 내 주석을 통해 알아보자. 

import Foundation

func solution(_ tickets:[[String]]) -> [String] {
    // 방문 여부를 기록하기 위한 배열 
    var visited = Array(repeating: false, count: tickets.count)
    // 문제의 조건에 맞게 우선적으로 도착 지점의 알파벳 순서대로 정렬시켜둔다. 
    var tickets = tickets.sorted { $0[1] < $1[1] }
    // 최종 결과 저장을 위한 배열 
    var result = [String]()

    func DFS(_ start: String) {
        // DFS의 값을 리턴하기 위함 
        if result.count == tickets.count {
            // 방문한 곳 개수와 전체 노선의 개수가 같다는 것은 현재 마지막 비행이라는 것
            // 이에 마지막 도착지를 append 해줌으로써 아래 tickets.count + 1에 걸리게 된다. 
            result.append(start)
            return 
        }
        // 재귀적으로 tickets를 처음부터 돌며 출발 지점과 같은지 찾기 위함 
        for i in 0..<tickets.count {
            // 출발 지점과 tickets[i][0]이 같고 아직 방문하지 않은 노선이라면 해당 노선을 선택하여 비행 
            if start == tickets[i][0] && !visited[i] {
                // 노선을 선택했으니 다녀간 노선으로 체크 
                visited[i] = true
                // 다녀간 노선이기에 출발지를 기록해둔다. 
                result.append(start)
                // 출발지는 result에 입력했으니 이제 도착지를 새로운 출발지로 하여 노선을 다시 선택해야 한다. 
                DFS(tickets[i][1])
                // 다녀간 지점들의 개수가 노선의 개수 + 1개라면 결과값 리턴 
                // 노선은 두 개가(A,B) 한 쌍이기에 + 1 해줘야 다녀간 지점들의 개수와 같아진다. 
                if result.count == tickets.count + 1 {
                    return       
                }
                // 모든 노선을 들르지 못하는 경우, 이전 출발지부터 다시 시작 (출발지점 회수, 방문표기 취소)
                result.removeLast()
                visited[i] = false 
            }   
        }
    }

    DFS("ICN")
    return result
}

 

예를 들어 경로 배열이 [("A","B"),("A","C"),("C","A")] 이와 같이 주어졌다면 2가지 경우의 수가 존재한다. 

 

• A > B 
• A > C > A > B

첫 번째의 경우 모든 노선을 지나치지 않아 조건에 충족되지 않는다. 즉 알파벳 순서가 빠르다고 무조건 좋은 것은 아니라는 것이다. 이에 B를 선택했던 것을 취소하는 것이 result.removeLast()와 visited[i] = false 부분이 된다. 그 이후 C를 선택하여 조건에 맞는 경로로 방문한 것을 알 수 있다. 

---

같은 DFS 문제여도 일부 조건이 붙는 순간 변형이 조금 생기는 것 같다. 이 문제는 오히려 순서가 핵심이었고, 불완전한 노선을 거를 수 있는 조건들을 알맞게 설정하는 것이 중요했던 문제였다. 

불완전한 노선이 되었을 경우 다른 경우로 도전해봐야 하는데, 이를 구현하는데 애를 먹었다. 오히려 간단하게 for문을 돌며 찾아낸 것이 아이디어였다. for문을 사용하지 않는다면 firstIndex()를 활용하여 index를 구해 (start,end)에 접근 가능할 것 같다. 

 

끄읕