DFS/BFS를 이용한 알고리즘

아래 문제는 프로그래머스에서 제공하는 여행경로의 문제입니다🧑🏻‍💻

문제 제시

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력 예

[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]	["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

입출력 예 설명

예제 #1

["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

예제 #2

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

문제 해결

import Foundation

func solution(_ tickets:[[String]]) -> [String] {
    // 여행지의 도착지 알파벳 순 정렬
    let tickets = tickets.sorted { $0[1] < $1[1] }
    // 여행지를 방문했는지에 대한 판별 배열
    var count = Array(repeating: false, count: tickets.count)
    // 결과 배열
    var answer: [String] = []
    
    // 여행을 도는 재귀함수
    func trip(start: String) {
    	// 결과와 여행지의 수가 같으면 해당 여행지만 추가하고 탈출
        if answer.count == tickets.count {
            answer.append(start)
            return
        }
        // 여행지의 수만큼 반복문을 돌면서 재귀를 탐
        for i in 0..<tickets.count {
        	// 여행지가 같고 방문한적이 없으면 조건문 탐
            if start == tickets[i][0] && !count[i] {
            	// 결과 배열에 추가
                answer.append(start)
                // 방문기록 남김
                count[i] = true
          
                //재귀함수 호출
                trip(start: tickets[i][1])
                
                // 결과는 항상 티켓 카운트보다 1만큼 크기에 그렇다면 탈출
                // else에서는 여행지를 다 돌지 못하면 마지막 요소를 지워주고 방문기록 초기화시킴
                if answer.count == tickets.count + 1 {
                    break
                } else {
                    answer.removeLast()
                    count[i] = false
                }
            }
        }
    }
    
    trip(start: "ICN")
    
    return answer
}

사용된 개념

 - DFS/BFS

 - 반복/조건문

 - 재귀함수

 - 2차원 배열

문제 뒷담화

해당 문제는 이전에 했던 재귀함수 개념을 적용하였다.

위의 주석처럼 생각하고 로직을 구성하였다.

중요할점은 재귀를 돌면서 if else문을 생각해야한다.

처음 else문을 없이 구성하였는데 재귀를 다 돌지만 중복되어서 먼저 나오는 도착지를 가지고 모든 여행지를 다 돌 수 없을때가 있다.

이때문에 테스트 케이스를 실패하였다.

그래서 곰곰히 생각하보니 여행지를 다 돌지 못할때 조건을 주지 않았었다.

그래서 else문에서 여행지를 다 돌지 못하여서 추가가 되지 않았다면 제일 마지막 요소의 값부터 삭제하고 방문 체크한 부분도 다시 초기화 해줌으로써 모든 경우의 수를 돌 수 있도록 생각하였다.

어떻게보면 매번 모든 경우의 수를 돌지 않아도 되지만 시간복잡도 상으로 최악의 경우에는 제일 마지막에 해당 답이 들어 있을테니 다 돌아야한다는뜻이다.

그래도 깊이와 너비 우선 탐색에서는 해당 로직이 최선인것같다.