[Swift] Lv3. 여행경로 (dfs)

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

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

 

생각

경로를 찾아서 갔다가 아니라면 return 해주기

나라 전체 방문이 아니라 티켓을 모두 쓰는(방문하는) 문제였다.

dfs를 오랜만에 봤더니.. 어떻게 푸는지 까먹어서 많이 헤맸다..

 

코드

전역변수를 안쓰려고 하다보니 매개변수 넣는 부분이 너무 ~ 길어져서 조금 코드가 복잡해졌다.

 

1, 2번 테스트 케이스를 틀렸는데 아래 테케와 같이 마지막에 A-> C를 가야하는데 중간에 A->C를 가버리면

dict["C"] 를 접근할 때 에러가 발생한다.

사실 처음에 딕셔너리를 만들 때 "C"의 경우도 넣어주면 되지만, 분기처리로 처리했다.

 

input

[["ICN", "A"], ["A", "ICN"], ["ICN", "A"], ["A", "C"]]

output

["ICN", "A", "ICN", "A", "C"]

 

1. 다음 도착지에서 출발하는 티켓이 있을 때

2.다음 도착지에서 출발하는 티켓은 없지만 마지막 티켓일 때 

 

// cur: 현재지점
// route: 현재까지의 경로
// count: 경로가 String 이라서 갯수 세기가 귀찮아서 변수로 던져줬습니다.
// endCount: 탈출조건
// dict: 티켓 (사용여부 변환을 위해서 inout)
func dfs(_ cur: String, _ route: String, _ count: Int, _ endCount: Int,
         _ dict: inout Dictionary<String, [(String, Bool)]>,
         _ answer: inout [String])  {
    if count == endCount {
        answer.append(route)
        return
    }

    for i in 0..<dict[cur]!.count {
        if !dict[cur]![i].1 {
            dict[cur]![i].1 = true
            let next = dict[cur]![i].0
            
            // 출발지에는 없고 도착지에만 있는 나라가 있기 때문에 구분해줬습니다.
            if let _ = dict[next] {
                dfs(next, route + " " + next, count + 1, endCount, &dict, &answer)
            } else if count == endCount - 1 {
                dfs(next, route + " " + next, count + 1, endCount, &dict, &answer)
            }
            dict[cur]![i].1 = false
        }
    }
}

func solution(_ tickets:[[String]]) -> [String] {
    var dict: Dictionary<String, [(String, Bool)]> = [:]
    var answer: [String] = []
    
    // 티켓을 딕셔너리 형태로 저장 [출발지 : [(도착지, 사용여부)]]
    for ticket in tickets {
        let start = ticket[0], next = ticket[1]
        if let _ = dict[start] {
            dict[start]!.append((next, false))
        } else {
            dict[start] = [(next, false)]
        }
    }
    
    dfs("ICN", "ICN", 1, tickets.count + 1, &dict, &answer)
    answer.sort()
    return answer[0].split(separator: " ").map { String($0) }
}