2023. 10. 25. 18:24ㆍ알고리즘/문제풀이
예제 1
3 1
4 4 2
ans :
2
4
예제 2
4 2
9 7 9 1
ans :
1 7
1 9
7 1
7 9
9 1
9 7
9 9
예제 3
4 4
1 1 1 1
ans : 1 1 1 1
백트래킹에 대한 설명 없이 바로 풀이를 할 예정입니다. 기본 백트래킹 코드를 잘 모르거나 백트래킹이 익숙하지 않으면 아래 게시글을 꼭 읽어보길 바랍니다!!
다른 N과 M 시리즈들과는 다르게 난이도가 높아진 게 갑자기 느껴진다. 이번에는 풀이를 정성스레 떠올려야 할 것 같다. 우선 트리를 그려보면서 언제 중복을 제거해야 좋을지 생각해 보자.
말로 설명하려 하니 좀 꼬이는데, 같은 길이의 항에 대해(같은 값의 k에 대해) 이전에 구한 수열의 마지막 항과 현재 방문하려 하는 항이 같으면 중복이라는 뜻이다. 이 트리 그대로 구현해 주면 된다.
func(k+1)을 호출하기 전에 현재 항과 비교에 사용될 temp 값에 수열의 마지막 항을 넣는다. temp = arr[i] 부분이 되겠다. 그리고 func(k+1) 호출이 끝나면 호출 전의 i값에 대한 수열은 모두 구했을 것이고, 다음 for문에서 i번째 숫자를 방문하지 않았고 temp와 다르다면 다른 수열이다. if(! visited[i] && temp!= arr[i]) 부분이다. 만약 temp == arr[i] 라면 arr[i]가 이전 for문 단계에서 구한 수열의 마지막 항과 같으므로 현재 arr[i]를 부모로 하는 모든 자식들이 중복이므로 방문하지 않는다.
/** BackTracking 15663 N과 M (9) **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int arr[10];
int res[10];
bool visited[10];
int n, m;
void func(int k)
{
if (k == m)
{
for (int i = 0; i < m; i++)
cout << res[i] << ' ';
cout << '\n';
return;
}
int temp = 0;
for (int i = 0; i < n; i++)
{
if (!visited[i] && temp != arr[i])
{
temp = arr[i];
res[k] = arr[i];
visited[i] = true;
func(k + 1);
visited[i] = false;
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> arr[i];
sort(arr, arr + n);
func(0);
}
'알고리즘 > 문제풀이' 카테고리의 다른 글
[BOJ] C++ 1941: 소문난 칠공주 - BFS와 백트래킹 섞어 쓰기 (0) | 2023.10.30 |
---|---|
[BOJ] C++ 6603: 로또 - 일반적인 BFS (0) | 2023.10.25 |
[BOJ] C++ 15655 N과 M (6) - 제한이 까다로운 백트래킹 (0) | 2023.10.25 |
[BOJ] C++ 1182 부분수열의 합 - 백트래킹 구현하기 (1) | 2023.10.18 |
[BOJ] C++ 9633 N-Queen - 백트래킹 구현하기 (1) | 2023.10.18 |