섹션 8. DFS, BFS 활용 6. 순열 구하기

문제

• 10 이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다.

입력

• 첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N)이 주어집니다.
• 두 번째 줄에 N개의 자연수가 오름차순으로 주어집니다.

출력

• 첫 번째 줄에 결과를 출력합니다.
• 출력순서는 사전순으로 오름차순으로 출력합니다.

입출력 예제

---

풀이방식

이번 문제는 DFS에 대한 문제이다.

---

설계과정

1. L과 M이 같으면 결과를 출력한다.

2. 이전에 방문하지 않은 노드이면 ch배열에 1을 넣고 pm[L] = arr[i] 를 넣는다.

3. DFS(L+1) 을 통해 다음 레벨로 이동하고, 그 후에는 돌아가면서 ch배열에 0을 넣어서 방문 기록을 없앤다.

---

풀이과정

1. 각 변수들을 선언 및 초기화한다.

• ch[ ] : 중복을 확인하기 위한 배열이다.
• pm[ ] : 각 레벨 당 M개의 원소를 저장하기 위한 배열이다.
• arr[ ] : 1부터 N까지의 수를 넣을 배열이다.

2. L이 M과 동일하면 결과를 출력한다.

• L은 레벨을 의미한다.
• 트리에서 마지막 노드가 위치한 레벨 즉, 마지막 레벨까지 도달하면 그동안 pm에 저장된 2개의 수를 출력한다.

3. 해당 노드를 방문한 적이 없으면, ch 배열에 1을 넣어주고 pm[L] = arr[i] 를 수행한다.

• ch 배열에 1을 넣어서 방문했다는 값을 넣어준다.
• pm[L] 즉, 예제에서 M이 2 이므로 0,1,2 각 레벨에 해당하는 수 arr[i] 를 넣어준다.

4. DFS를 재수행하되, L+1로 파라미터를 넘긴다.

• 다음 레벨에 대해 탐색해야하기 때문이다.

5. 탐색을 완료한 후에 이전 레벨로 돌아가기 위해서 ch 배열에 0을 넣어준다.

• 현재 레벨은 방문하지 않은 노드만이 존재하도록 만들기 위함이다.

---

더 자세한 설명은 아래 글을 참조해서 확인해보기 바랍니다.

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.