초니로그

문제 링크 - https://www.acmicpc.net/problem/15649

문제 설명

n, m이 주어지면 1이상 n이하의 수 중 m개를 선택해 구성한 순열 출력

n >= m이며, n과 m 모두 1이상 8이하의 정수

풀이법 구상

파이썬을 사용하면 itertools 내 permutations 메소드를 써서 바로 풀이가 가능하지만 스위프트는 그런거 없음 왜..왜...

처음에는 1부터 n까지의 정수가 담긴 배열을 돌면서 하나씩 추가하고 배열에서 삭제해나가는 로직으로 생각했는데, 이러면 m중 반복문을 돌아야함 (그래도 시간복잡도가 O(N^m)이라 시간초과는 안 나겠지만 구현하기 까다로울 것 같아서 일단 포기)

1이상 n이하 정수 중에서 m개를 뽑는 방법은 DFS/BFS를 사용할 수 있는데

n이 4이고, m이 2인 경우를 생각해보면 1부터 4사이의 정수 중에 2개를 선택해야함

선택된 수를 담을 배열은 아래와 같은 경우의 수들을 가질 수 있음

[ ] -> [1] -> [1,2]

[ ] -> [1] -> [1,3]

[ ] -> [1] -> [1,4]

[ ] -> [2] -> [1,2]

[ ] -> [2] -> [2,3]

[ ] -> [2] -> [2,4]

...

[ ] -> [4] -> [3,4]

위 경우들은 트리로 시각화 할 수 있고, 각 노드들을 탐색하면서 노드를 구성하는 정수배열의 크기가 m인 경우만 중복없이 출력시키면 됨

는 그나마 익숙한 BFS로 구현했더니 시간초과

/// 시간초과난 코드

import Foundation

func solution(_ n: Int, _ m: Int) -> Void {
    var results: [[Int]] = []
    for i in 1...n { results.append([i]) }

    // 수열 생성
    for _ in 0..<m {
        for arr in results {
            var temp: [[Int]] = []
            for i in 1...n {
                if arr.contains(i) { continue }
                var temp_arr = arr
                temp_arr.append(i)
                temp.append(temp_arr)
            }
            
            for t in temp {
                if !results.contains(t) { results.append(t) }
            }
        }
    }

    // 사전 순으로 정렬
    var sorted_results: [[Int]] = []
    for arr in results { if (arr.count == m) { sorted_results.append(arr) } }
    
    sorted_results = sorted_results.sorted(by: { $0[0] < $1[0] })

    // 정답 출력
    for arr in sorted_results {
        var str = ""
        for a in arr { str += "\(a) " }
        print(str)
    }
}

let input = readLine()!.components(separatedBy: " ")
solution(Int(input[0])!, Int(input[1])!)

구글링했더니 대부분 백트래킹으로 풀었음

백트래킹은 DFS와 비슷하지만 DFS는 종료 조건만 가지고 무지성 재귀함수를 사용하고, 백트래킹은 답이 있을 것 같은 경우에만 탐색하는 것이 차이점임

백트래킹에서 쓰이는 '유망함', '유망하지않음', '가지치기'의 용어도 정답 존재 가능성과 연관된 것임

- 유망함 : 정답을 찾을 수 있는 가능성 O

- 유망하지않음 : 정답을 찾을 가능성 X

- 가지치기 : 유망하지 않은 경우를 제외하는 것

(아무튼 다시 이 문제로 돌아와서) BFS 풀이는 배열의 수가 0개 -> 1개 -> 2개 -> ... -> m개인 순서로 노드들을 탐색하기 때문에, 배열의 길이가 0개부터 m-1개인 탐색할 필요가 없는 경우까지 고려하게 됨

그리고 모든 결과 배열을 다 포함하고 마지막에 탐색하면서 길이가 m인 배열을 사전순으로 출력하기 위해 따로 정렬도 해줘야 함

근데 백트래킹 풀이는 가장 적은 숫자부터 구성된 배열 중, 길이가 m인 경우에만 출력하게 하면 되니까 불필요한 경우의 고려와 정렬 코드가 삭제될 수 있음

그럼 백트래킹을 쓰려면 뭐가 유망한 거고, 뭐가 유망하지 않은 건지를 알아야 하는데 n = 4, m = 2인 경우를 예시로 보면, 

결과배열이 [1]인 경우에는 1부터 4까지 중 1을 제외하고 추가해야함

이런 생각들로 아래처럼 구현하고 제출했더니 성공,,

코드 구현 (스위프트 사용)

import Foundation

func solution(_ n: Int, _ m: Int) -> Void {
    let temp:[Int] = []
    dfs(arr: temp, m: m, n: n)
}

func dfs(arr: [Int], m: Int, n: Int) -> Void {
    if (arr.count == m) {
        var str = ""
        for a in arr { str += "\(a) " }
        print(str)
        return
    }

    var temp = arr
    for p in 1...n {
        if !temp.contains(p) {
            temp.append(p)  // 1부터 n 사이의 배열에 없는 숫자 중 젤 작은 거 추가
            dfs(arr: temp, m: m, n: n)   // 위에서 숫자 새로 추가한 배열로 다시 검사
            temp.remove(at: temp.count-1)   // 위에서 검사 끝나고 오면 가장 최근에 추가했던거 삭제(그 자리에 다른 새로운거 넣어보려고)
        }
    }
}

let input = readLine()!.components(separatedBy: " ")
solution(Int(input[0])!, Int(input[1])!)

DFS/BFS로 풀 수 있을 것 같아도 시간 복잡도 한 번 더 고려해보고, 뭔가 될 것 같아서 풀었는데 시간초과나면 백트래킹 풀이도 고려해보자