[프로그래머스] (Swift) 여행경로 (lv.3) (DFS, Well-Known 기억해주세욤)

아아아 짜증나 잘 안풀려ㅠㅠ 예전에 내가 풀었던 코드를 잠깐 참고하고 풀었씀... 흡.. 🤥

 

⚫️ 문제

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

프로그래머스

 

⚫️ 나의 풀이

일단 보자마자 DFS임을 파악하긴 했는데... 잘 안풀렸다. 시작지점이 ICN으로 지정되어있었는데, dfs에 ICN을 전달하면, 티켓의 첫번쨰원소가 ICN인걸 찾아야하는건가? 싶어서 고민했고, 그 이후에 모든 경우를 다 판단하고 answer에 쌓아야하는데 어떻게 하지.. 그냥 고민이었다. 

결국 알고리즘을 떠올리는건 가능햇지만, 이를 구현하는 능력이 부족했다. 5개월전에 풀어본 문제였지만,, 생각이 나지 않았다 ㅠㅠ 
이 문제는 dfs에 start 지점을 던져주는 것으로 시작하면 된다. 

처음에 ICN을 던져줬으니, for 문을 돌려서 ticket내부에서 start지점이 ICN이랑 동일한 티켓을 찾는다. 그리고 그 티켓이 만약 사용되지 않은 티켓이라면, 그 티켓부터 사용하게 된다. 

티켓을 사용하고, 티켓에 있는 end 공항이, 다음 내가 방문할 start 공항이 되겟지? 그럼 여기서 DFS에 end를 전달해서 다시 재귀를 돌려주면 된다. 이 다음이 좀 까다로웠던 부분인데, 재귀의 구조를 잘 생각해야했다. 재귀를 타고타고 들어가서, 차례대로 return 해나온다. 특정 조건, 즉 여기서는 모든 티켓을 다 사용했으면 맨 하위에있는 dfs 함수가 return 될 것이고, 그렇게 나오게 되면 다시 그 윗단계 dfs함수부분으로 넘어가게된다. 그때, visited는 false처리를 해주면서 넘어가야하고 answer로 쌓아놧던 값들도 하나씩 지워가면서 앞의 dfs 함수로 넘어가주어야한다. 그래야 다음 for문을 돌때 정상적인 상태로 돌수있으니까!

⚫️ 정답 코드

import Foundation

let tickets = [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]
// return : ["ICN", "JFK", "HND", "IAD"]

func solution(_ tickets:[[String]]) -> [String] {
    var answer = [String]()
    var visited = Array(repeating: false, count: tickets.count)
    let tickets = tickets.sorted{ $0[1] < $1[1] }

    // MARK: - DFS 함수
    func dfs(airport: String) {
        // 만약 모든 티켓이 다 사용되고 마지막 end 지점이라면?
        if tickets.count == answer.count {
            answer.append(airport)
            return
        }

        for i in 0..<tickets.count {
            let start = tickets[i][0]
            let end = tickets[i][1]

            if airport == start, !visited[i] {
                visited[i] = true
                answer.append(start)
                dfs(airport: end)
                if tickets.count + 1 == answer.count {
                    return
                }
                visited[i] = false
                answer.removeLast()
            }
        }
    }

    dfs(airport: "ICN")

    return answer
}

print(solution(tickets))

 

이 코드 구조를 잘 기억해두자. DFS 의 일반적인 형태이기도 하다. return 해나오면서 false처리를 해주고, answer에 있는 것들을 하나씩 없애주는 과정도 꼭 잊지말고 구현해주자. 아직 재귀에 대한 이해가 떨어지는 나는, 이부분을 생각해내는게 가장 어려웠다. 

LV3라서 엄청난 스킬을 요구할것 같은 문제였지만, 사실 그냥 기본중의 기본문제였다. 꼭 다시풀어보고, 기억해주자 ㅠㅠㅠ 화이팅.