15663번: N과 M (9)

문제 풀이 아이디어

N과 M이 숫자가 올라갈 수록 조금씩 복잡해지고 있습니다. 고지가 멀지 않았네요. 이번 문제는 중복체크를 구현해야 합니다. 다양한 중복체크 방법이 있겠지만 저는 Set을 활용해서 중복체크를 해보겠습니다.

코드

// 입력 받기
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0], M = input[1]
let array = readLine()!.split(separator: " ").map { Int(String($0))! }.sorted()
    //👉 숫자는 정렬하기

// 방문 체크 배열
var visited = Array(repeating: false, count: N)
// 탐색 결과 저장 배열
var result = [String]()
// 수열이 중복되는지 체크하는 배열
var check = Set<String>()

// dfs 구현
func dfs() {
    // 탈출 조건
    if result.count == M {
        // 중복 체크해서 중복되지 않으면 출력
        let resultString = result.joined(separator: " ")
        if !check.contains(resultString) {
            check.insert(resultString)
            print(resultString)
        }
        return
    }
    
    // 방문체크 하면서 완전탐색
    for i in 0..<N {
        if !visited[i] {
            visited[i] = true
            result.append(String(array[i]))
            dfs()
            visited[i] = false
            _ = result.popLast()
        }
    }
}

dfs()