티스토리 뷰
#. Problem
* The copyright in this matter is in Inflearn
#. Resolution Process
1. Read and understand problem
2. Redefine the problem + abstract
- 자연수 N과 R이 주어지면, 서로 다른 N개의 자연수 중 R개를 뽑아 일렬로 나열
3. Create solution plan (select Algorithm, Data structure)
4. Prove the plan (check performance time and usage memory)
5. Carry out the plan
6. Look back on the plan and find a way to improve it
#. Solve
전형적인 DFS 문제이다.
하지만, DFS 문제를 안 풀다보니 가물가물하기도 하고..
모든 경우의 수를 확인해야 하므로
N의 개수만큼 계속 DFS가 깊어진다.
여기서 check 배열을 활용하여 이미 사용된 자연수면 pass하고 사용되지 않은 자연수일 경우만 사용해주면
수열이 완성될 수 있을 것이다.
입력이 아래와 같을 떄,
4 3
1 3 6 7
아래 그림처럼
1번 idx가 사용되고 2,3,4번 idx가 사용될 수 있다. (1은 이미 사용되었으므로 pass)
1번-2번 idx를 사용했을 때, 다음을오 3번 or 4번 idx 가 사용될 수 있다.
이와 같은 방식으로 DFS 함수를 구현해보면 되겠다.
대략적인 코드를 생각해보자.
DFS(int lv) // level이 3에 도달했을 때, 자연수가 3개 사용된 것이므로 인자는 level 이 되면 좋을 것이다.
{
if(lv == r) // levle이 r과 같다면 사용된 자연수를 출력해주자.
{
}
else // 같지 않다면 재귀함수를 돌려줘야하는데, 모든 자연수를 확인해야하므로
{
for(i=1; i<=n; i++) // n의 크기만큼 반복문이 필요할 것 같다.
{
if(ch[i] == 0) // i번째 idx의 자연수가 사용되지 않았다면,
{
ch[i] = 1; // 체크해준 후
DFS(lv + 1); // DFS에 level을 +1 해주고 호출
DFS[i] = 0; // 할 일을 마쳤으므로 체크를 풀어준다.
}
}
}
}
여기까지 왔는데 이제 출력이 문제다.
ch[] 배열에 체크된 자연수만 확인해서 출력한다면,
만일 1, 3, 6 이 사용되었을 때,
{1 3 6}, {1 6 3}, {6, 1, 3}, {6, 3, 1} 이 모두 {1, 3, 6} 으로 출력될 것이다.
출력할 때도 for 문을 상용할 터이니..
그러므로 출력을 담당하는 배열로 필요할 것 같다.
DFS(int lv) // level이 3에 도달했을 때, 자연수가 3개 사용된 것이므로 인자는 level 이 되면 좋을 것이다.
{
if(lv == r) // levle이 r과 같다면 사용된 자연수를 출력해주자.
{
for(i=0; i<r; i++) // 사용할 자연수의 개수만큼 반복하는데, level 0부터 시작했으므로 idx 0부터 시작
printf("%d ", prt[i]);
puts("");
rst++; // 출력해주고 총 개수도 카운트해준다.
}
else // 같지 않다면 재귀함수를 돌려줘야하는데, 모든 자연수를 확인해야하므로
{
for(i=1; i<=n; i++) // n의 크기만큼 반복문이 필요할 것 같다.
{
if(ch[i] == 0) // i번째 idx의 자연수가 사용되지 않았다면,
{
prt[lv] = a[i]; // 해당 level 에서는 i번째 자연수를 사용하겠다.
ch[i] = 1; // 체크해준 후
DFS(lv + 1); // DFS에 level을 +1 해주고 호출
DFS[i] = 0; // 할 일을 마쳤으므로 체크를 풀어준다.
}
}
}
}
#. Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; int n, r, rst = 0, a[16], ch[16], prt[16]; void DFS(int cnt) { int i; if (cnt == r) { for (i = 0; i < r; i++) printf("%d ",prt[i]); puts(""); rst++; } else { for (i = 1; i <= n; i++) { if (ch[i] == 0) { prt[cnt] = a[i]; ch[i] = 1; DFS(cnt + 1); ch[i] = 0; } } } } int main(void) { freopen("input.txt", "rt", stdin); int i; scanf("%d %d", &n, &r); for (i = 1; i <= n; i++) scanf("%d", &a[i]); DFS(0); printf("%d\n", rst); return 0; } | cs |
#. Other code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | #include<stdio.h> using namespace std; int n, r, cnt=0; int a[20], res[20], ch[20]; void DFS(int L){ if(L==r){ for(int j=0; j<L; j++){ printf("%d ", res[j]); } cnt++; puts(""); } else{ for(int i=1; i<=n; i++){ if(ch[i]==0){ res[L]=a[i]; ch[i]=1; DFS(L+1); ch[i]=0; } } } } int main(){ scanf("%d %d", &n, &r); for(int i=1; i<=n; i++){ scanf("%d", &a[i]); } DFS(0); printf("%d\n", cnt); return 0; } | cs |
line 7~25) DFS 함수를 살펴보자.
line 8~14) level이 r과 같다면, 사용된 자연수들을 출력하고 cnt++
line 15~24) level이 r과 다르다면, 1부터 n까지 자연수들을 다 사용해본다.
단, 이미 사용된 자연수라면 pass해주고 사용되지 않은 자연수라면,
먼저 출력할 자연수를 저장하는 배열에 해당 자연수를 저장하고, 체크배열에 체크해준다.
그리고 그 다음으로 선택될 자연수를 탐색하기 위해 DFS 함수를 호출하는데,
인자로는 level 즉, 사용된 자연수의 개수를 넘겨준다.
재귀함수의 동작이 끝나면 체크를 풀어준다.
#. Result
- Input --------------------------------------------------------
4 3
1 3 6 7
------------------------------------------------------------------
- Output --------------------------------------------------------
1 3 6
1 3 7
1 6 3
1 6 7
1 7 3
1 7 6
3 1 6
3 1 7
3 6 1
3 6 7
3 7 1
3 7 6
6 1 3
6 1 7
6 3 1
6 3 7
6 7 1
6 7 3
7 1 3
7 1 6
7 3 1
7 3 6
7 6 1
7 6 3
24
------------------------------------------------------------------
'PS > Problem_Solving' 카테고리의 다른 글
| [Inflearn] 수식만들기(삼성 SW역량평가 기출 : DFS) (0) | 2020.05.09 |
|---|---|
| [Inflearn] 휴가(삼성 SW역량평가 기출 - DFS) (c/c++) (0) | 2020.05.09 |
| [Inflearn] 친구인가? (Union & Find 자료구조)(c/c++) (0) | 2020.05.05 |
| [Inflearn] 이항계수(메모이제이션)(c/c++) (0) | 2020.05.04 |
| [Inflearn] 최대 수입 스케쥴(priority_queue 응용) (3) | 2020.05.04 |