10974번: 모든 순열

순열 구현하기

파이썬 예시

저는 원래 파이썬으로 알고리즘 공부를 했었는데요. 파이썬으로 풀 당시에는 이 문제는 전혀 난이도 있는 문제가 아니었습니다. 아래처럼 파이썬 자체에 내장되어 있는 순열함수를 이용해서 풀면 되었거든요.

from itertools import permutations

n = int(input())
nums = [i for i in range(1, n + 1)]

for permutation in permutations(nums, n):
    for num in permutation:
        print(num, end=" ")
    print()

스위프트에서는?

하지만 스위프트에서는 위와 같은 내장 함수가 존재하지 않습니다. 그래서 순열 함수를 직접 구현해서 사용해야 합니다. 재귀함수(정확히는 dfs)의 개념을 알아야 하죠. 주석으로 설명해보도록 할께요.

// 순열을 구하는 함수
	//👉 array: 순열을 구하고자 하는 대상을 array에 담아 인자로 전달
	//👉 length: 순열의 길이를 전달
func permutations<T: Comparable>(of array: Array<T>, length: Int) -> [[T]] {
    var result = [[T]]() //👉 결과를 담을 함수
    var visited = Array(repeating: false, count: array.count)
		//👉 dfs에서 visit 여부를 담는 함수
    
	// dfs를 수행하는 함수
    func permute(_ now: Array<T>) {
		// 재귀함수 탈출 조건 = 순열의 길이가 충족 되었을 때
        if now.count == length {
            result.append(now) //👉 결과 array에 담기
            return
        }
		// array 안을 순회하면서
        for i in 0..<array.count {
			//👉 이미 방문한 경우 = 이미 순열 안에 있는 경우 = continue
            if visited[i] == true {
                continue
            }
			//👉 아직 방문하지 않은 경우
            else {
                visited[i] = true //👉 방문 표시하고 
                permute(now + [array[i]]) //👉 현재 순열에 추가해서 재귀함수
                visited[i] = false //👉 재귀함수 return 되면 방문 표시 해제
            }
        }
    }

    permute([]) //👉 실제 재귀함수 수행하기
    return result
}

문제 풀이

위에 작성한 순열 함수를 활용해서 문제를 풀어봅시다. forEach문을 2번 사용했습니다.

let N = Int(readLine()!)!
let nums = Array(1...N)

// 모든 순열을 순회하면서
permutations(of: nums, length: N).forEach { permutation in
    permutation.forEach { num in
        print(num, terminator: " ") // 해당 순열을 한 줄로 출력
    }
    print() // 하나의 순열이 끝나면 줄 바꾸기
}

참고한 블로그 🙏

스위프트 | "순열과 조합 구현"하기 (Swift5 | Permutation, Combination)

[Swift] 순열과 조합 구현