알고리즘 문제(Swift) - 프로그래머스: 여행 경로

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

프로그래머스

 

 

첫 번째 시도

• 우선, tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미이므로, 출발지에서 갈 수 있는 모든 도착지를 구분하기 위해 딕셔너리로 정의했다
• ICN에서 출발하여 갈 수 있는 도착지 중 알파벳 순으로 이동하고, 도착한 곳은 removeFirst() 로 딕셔너리의 value에서 제거하므로써 티켓을 사용 처리했다
  • mapValues : 딕셔너리에서 key는 유지하면서 value만 변환하는 함수
• 방문한 곳은 visited 배열에 추가하여 티켓의 수 보다 커질 때까지 반복했다

import Foundation

func solution(_ tickets:[[String]]) -> [String] {
		// 출발지에서 갈 수 있는 모든 도착지
    var dic: [String: [String]] = [:] // 딕셔너리 정의: [출발지: [도착지]]
    
    for ticket in tickets {
        let start = ticket[0]
        let end = ticket[1]
        if dic[start] == nil { // 해당 key가 없으면
            dic[start] = [end] // 새로 등록
        } else {
            dic[start]?.append(end) // 기존 key가 있으면 value 배열에 추가
        }
    }
    
    dic = dic.mapValues { $0.sorted() } // value 값 오름차순 정렬
    
    var visited: [String] = ["ICN"] // 방문한 곳
    var current = "ICN" // 현재 위치
    
    while visited.count < tickets.count + 1{ // 방문한 곳이 전체 티켓보다 크면 종료
        if let next = dic[current]?.removeFirst() { // 다음 갈 수 있는 도착지 중 알파벳이 빠른 곳을 방문 후 제거
            visited.append(next) // 방문 처리
            current = next // 현재 위치를 다음 위치로 변경
        }
    }
    return visited
}

→ 예제 통과, 테스트케이스 1, 2 시간 초과

• 다음 도착지를 선택할 때, 이동할 수 있는 곳이 아무곳도 남아있지 않다면(dic[current] == nil) 계속 while문만 반복할 뿐 visited가 증가되지 않아 while문을 종료할 수 없었다

 

두 번째 시도: 반복문 종료 추가

• 이동할 수 있는 곳이 남아있지 않다면 while 문을 종료하도록 break를 추가

import Foundation

func solution(_ tickets:[[String]]) -> [String] {
		// 출발지에서 갈 수 있는 모든 도착지
    var dic: [String: [String]] = [:] // 딕셔너리 정의: [출발지: [도착지]]
    
    for ticket in tickets {
        let start = ticket[0]
        let end = ticket[1]
        if dic[start] == nil { // 해당 key가 없으면
            dic[start] = [end] // 새로 등록
        } else {
            dic[start]?.append(end) // 기존 key가 있으면 value 배열에 추가
        }
    }
    
    dic = dic.mapValues { $0.sorted() } // value 값 오름차순 정렬
    
    var visited: [String] = ["ICN"] // 방문한 곳
    var current = "ICN" // 현재 위치
    
    while true{
        if let next = dic[current]?.first {
            dic[current]?.removeFirst() // 다음 갈 수 있는 도착지 중 알파벳이 빠른 곳을 방문 후 제거
            visited.append(next) // 방문 처리
            current = next // 현재 위치를 다음 위치로 변경
        } else { // 다음 도착지가 없으면 while문 종료
            break
        }
    }
    return visited
}

→ 시간 초과는 발생하지 않았지만, 테스트케이스 1, 2 실패

• 가능한 경로가 2개 이상일 경우, 무조건 알파벳 순서가 앞서는 곳을 향하도록 경로를 구성해도 답이 아닐 수 있다
• 예제
  • tickets: [["ICN", "AAA"], ["ICN", "CCC"], ["CCC", "DDD"], ["AAA", "BBB"], ["AAA", "BBB"], ["DDD", "ICN"], ["BBB", "AAA"]]
  • answer: ["ICN", "CCC", "DDD", "ICN", "AAA", "BBB", "AAA", "BBB"]
  • 알파벳 순으로 이동하면 ICN - AAA - BBB - AAA -BBB 로 끝이 나버린다

→ 따라서 알파벳 순으로 이동한 후 티켓을 모두 사용하지 못하면 알파벳 순이 아닌 다른 경로를 탐색해야 한다

 

세 번째 시도: 재귀함수로 변경

import Foundation

func solution(_ tickets:[[String]]) -> [String] {
        // 출발지에서 갈 수 있는 모든 도착지
    var dic: [String: [String]] = [:] // 딕셔너리 정의: [출발지: [도착지]]
    
    for ticket in tickets {
        let start = ticket[0]
        let end = ticket[1]
        if dic[start] == nil { // 해당 key가 없으면
            dic[start] = [end] // 새로 등록
        } else {
            dic[start]?.append(end) // 기존 key가 있으면 value 배열에 추가
        }
    }
    
    dic = dic.mapValues { $0.sorted() } // value 값 오름차순 정렬
    
    var visited: [String] = ["ICN"] // 방문한 곳
    
    // 재귀 함수
    func recur(_ current: String) -> [String] {
        if visited.count > tickets.count { // 방문한 곳이 티켓보다 많으면 방문한 곳 리턴
            return visited
        }

        if let next = dic[current]?.first { // 갈 수 있는 곳 중 알파벳 빠른 곳
            dic[current]?.removeFirst() // 갈 수 있는 곳에서 제거
            visited.append(next) // 방문한 곳에 추가
            let answer = recur(next) 
            
            if !answer.isEmpty { // == visited를 리턴 받았을 경우
                return answer
            } else { // 빈 배열을 리턴 받았을 경우 (이전 방문한 곳으로 돌아가야 함)
                visited.removeLast() // 방문한 곳 배열에서 현재 위치 제거
                dic[current]?.insert(next, at: 0) // 도착지에 다시 추가
                return []
            }
        }
        
        return []
    }
    return recur("ICN")
}

→ 시간 초과는 발생하지 않았지만, 테스트케이스 1, 2 실패

• 재귀함수로 변경했지만, 방문할 곳이 없을 때 계속 return [] 되어 함수가 종료된다 (첫 번째 도착지로만탐색)
• 도착지가 여러 곳일 때, 첫 번째 도착지로 경로 연결에 실패하면 다음 도착지로 경로를 연결해야 한다
• 가능한 도착지를 모두 탐색하야 한다

 

 

네 번째 시도: 모든 도착지 경로 탐색

• 현재 위치에서 갈 수 있는 경로 모두 탐색 (for 사용)
  • 갈 수 있는 경로가 없을 경우 return []
• 경로를 완성하지 못해 다시 돌아갈 때, 이전 모습 그대로 돌아가야 된다고 생각해서 insert를 이용해 기존에 있던 맨 앞자리로 추가했다
• → 다음 방문할 때 똑같은 곳을 방문함
• append로 변경하여 맨 앞이 아닌 맨 뒤로 보내야 다음 방문 때, 방문하지 않은 곳을 방문할 수 있다

import Foundation

func solution(_ tickets:[[String]]) -> [String] {
        // 출발지에서 갈 수 있는 모든 도착지
    var dic: [String: [String]] = [:] // 딕셔너리 정의: [출발지: [도착지]]
    
    for ticket in tickets {
        let start = ticket[0]
        let end = ticket[1]
        if dic[start] == nil { // 해당 key가 없으면
            dic[start] = [end] // 새로 등록
        } else {
            dic[start]?.append(end) // 기존 key가 있으면 value 배열에 추가
        }
    }
    
    dic = dic.mapValues { $0.sorted() } // value 값 오름차순 정렬
    
    var visited: [String] = ["ICN"] // 방문한 곳
    
    // 재귀함수
    func recur(_ current: String) -> [String] {
        if visited.count > tickets.count {
            return visited
        }
        
        guard let nexts = dic[current] else { return [] } // 갈 수 있는 모든 경로

        for next in nexts { // 갈 수 있는 모든 경로 탐색
            dic[current]?.removeFirst() // 갈 수 있는 곳에서 제거
            visited.append(next) // 방문한 곳에 추가
            let answer = recur(next)
            
            if !answer.isEmpty {  // == visited를 리턴 받았을 경우
                return answer
            } 
            visited.removeLast()  // 방문한 곳 배열에서 현재 위치 제거
            
        //  dic[current]?.insert(next, at: 0) // 기존 위치에 다시 추가
            dic[current]?.append(next) // 기존 위치가 아닌 맨 뒤에 추가
        }
        return []
    }
    return recur("ICN")
}

 

 

회고

• 처음 문제를 봤을 떄, ‘이 문제는 재귀함수를 이용하여 해결해야겠다’가 바로 떠오르지 않았다. 이 이유는 물론 DFS/BFS 문제를 많이 풀어보지 않아서지만, 제한사항과 예제에 나와있지 않은 다른 케이스 (알파벳 순서의 경로가 모두 답이지 않다)를 찾는 연습이 필요해보인다
• 재귀함수의 동작이 코드를 작성하면서 바로바로 생각나지 않는다. 잘못된 코드라도 완성해야 실행되는 과정이 머릿속에 들어온다. 많은 연습이 필요해보인다