스위프트 DFS 백트래킹 예제, 백준 10974 모든순열 풀이

 

 

 

 

---

백준 10974번 모든 순열 예제설명

백준 10974번 모든순열은 N이 주어졌을 때 1부터 N까지의 수를 가진 모든 순열을 사전순으로 출력하는 문제입니다. 본 문제는 재귀 / 비재귀 방식으로 모두 풀 수 있는 문제입니다.

 

 

 

 

시간제한은 1초, 메모리제한은 256MB입니다. 모든ㄴ순열의 출력은 DFS, 백트래킹을 사용해서 출력해볼 예정입니다.

 

N의 범위가 최대 8이므로, N!의 시간복잡도로도 충분히 풀리는 문제입니다. 최대 값인 8의 경우에도 최대 1억번의 연산에 미치지 않기 때문입니다.

 

 

 

 

위와 같이 N이 3일 경우, 1, 2, 3 세개의 숫자가 있는 모든 순열을 사전순, 개행단위로 출력해주면 되는 문제입니다.

이어서 swift언어와 DFS(깊이 우선 탐색) 백트래킹을 활용해서 문제를 풀어보도록 하겠습니다.

 

 

 

 

---

백준 10974번, 모든순열 예제 스위프트 문제풀이
DFS 백트래킹 재귀를 통한 문제풀이 방법

스위프트 언어로 문제 바로 풀어보겠습니다. 먼저, 입력을 받고, 필요한 변수/상수를 준비하는 단계입니다. 

2행) N을 입력받습니다. 

 

3행) 1...N의 숫자가 있는 리스트를 하나 만들었습니다. 

4행) 만들어진 임시순열을 저장할 배열 result입니다.

 

5행) 순열에는 중복된 숫자가 들어가면 안되죠. 순열에 중복숫자가 들어가지 않도록, 가지치키(백트래킹) 하기위해서 사용하는 배열입니다. 

6행) 순열 리스트를 가진 정답이 들어갈 배열입니다.

 

 

 

 

---

배열 익스텐션, Array extension의 활용

Array extension을 활용해서 문제를 풀수도 있습니다. extension의 장점은 해당 배열의 기능을 명확히 구분해서 정의할 수 있다는 점과, 배열 인자값이 하나 빠진 메서드를 만들 수 있어서 인자 복잡도가 줄어드는 장점이 있습니다.

 

9 ~ 11행) appendValueString은 발견한 순열을 answer에 추가하는 기능입니다.

13 ~ 15행) printAnswer 메서드는 answer 정답을 마지막에 개행단위로 출력할때 사용할 기능입니다.

 

17 ~ 21행) DFS 백트래킹을 구현한 핵심 메서드입니다. 기저조건(재귀 종료조건)은 result의 크기가 N이 됐을때입니다. 이때 만들어진 순열을 하나하나 answer에 쌓아둡니다. 

 

23 ~ 31행) 백트래킹과 재귀를 호출하는 부분입니다. 숫자중복은 dic으로 체크해서 중복일 경우 해당 케이스의 재귀는 호출하지 않습니다. 중복되지 않은 수라면 result에 적재하고 재귀를 호출합니다. 재귀가 종료했을때는 다음 케이스 재귀체크를 위해 원 상태로 복귀시킵니다. (28 ~ 29행)

 

 

 

 

위의 DFS코드를 실행하고, 모든 순열을 사전순으로 출력하는 코드입니다. 

이렇게 최종적으로 1 ~ N까지의 숫자를 가진 모든 순열을 사전 순으로 출력할 수 있습니다.위 코드의 제출결과는 아래와 같습니다. 

 

해당 방법이 최선은 아닙니다. 재귀없이도 순열을 구할 수 있습니다. 순열을 만들때 재귀를 사용해서 구할 수 있다는것이 본 포스팅의 목적입니다.

 

 

 

---

백준 10974번, 모든순열 예제 스위프트 문제풀이