6603번: 로또

문제 풀이 아이디어

조합의 개념을 적용해서 풀면 되는 문제입니다.

파이썬 같이 내부적으로 combination을 지원하는 언어라면 훨씬 쉽게 풀 수 있겠지만 Swift는 지원하지 않기에 직접 구현하거나 다른 경우의 수를 다루는 알고리즘을 사용해서 풀어야 합니다.

여기서는 dfs를 활용해서 풀어보도록 하겠습니다. dfs는 완전탐색 알고리즘이므로 모든 경우의 수를 구해야 할 때 유용하게 사용할 수 있습니다.

코드

dfs 내부에 결과값을 가진 경우

// dfs 내부에 결과값을 가지고 있는 경우
while true {
    func dfs(now: [Int], index: Int, depth: Int) {
        if depth == 6 {
            for num in now {
                print(num, terminator: " ")
            }
            print()
            return
        }
        
				//🚫 방문체크를 할 필요가 없는 이유는 index부터 탐색하므로
        for i in index..<k {
            dfs(now: now + [S[i]], index: i + 1, depth: depth + 1)
        }
    }
    
    var S = readLine()!.split(separator: " ").map { Int(String($0))! }
    let k = S.removeFirst()
    if k == 0 { break }
    dfs(now: [], index: 0, depth: 0)
    print()
}

dfs 외부에 결과값을 두는 경우

while true {
    func dfs(index: Int, depth: Int) {
        if depth == 6 {
            for num in result {
                print(num, terminator: " ")
            }
            print()
            return
        }
        
        for i in index..<k {
            result.append(S[i])
            dfs(index: i + 1, depth: depth + 1)
            _  = result.popLast()!
        }
    }
    
    var S = readLine()!.split(separator: " ").map { Int(String($0))! }
    let k = S.removeFirst()
    if k == 0 { break }
    var result = [Int]()
    dfs(index: 0, depth: 0)
    print()
}